Modify given array to make sum of odd and even indexed elements same

0 0 8 minutes read

Given a binary array arr[] of size N, remove at most N/2 elements from the array such that the sum of elements at odd and even indices becomes equal. The task is to print the modified array.
Note: N is always even. There can be more than one possible result, print any of them.

Examples:

Input: arr[] = {1, 1, 1, 0}
Output: 1 1
Explanation:
For the given array arr[] = {1, 1, 1, 0}
The sum of elements at odd position, Odd_Sum = arr[1] + arr[3] = 1 + 1 = 2.
The sum of elements at even position, Even_Sum = arr[2] + arr[4] = 1 + 0 = 1.
Since Odd_Sum & Even_Sum are not equal, remove some elements to make them equal.
After removing arr[3] and arr[4] the array become arr[] = {1, 1} such that sum of elements at odd indices and even indices are equal.

Input: arr[] = {1, 0}
Output: 0
Explanation:
For the given array arr[] = {1, 0}
The sum of elements at odd position, Odd_Sum = arr[1] = 0 = 0.
The sum of elements at even position, Even_Sum = 1 = 1.
Since Odd_Sum & Even_Sum are not equal, remove some elements to make them equal.
After removing arr[0] the array become arr[] = {0} such that sum of elements at odd indices and even indices are equal.

Approach: The idea is to count the number of 1s and 0s in the given array and then make the resultant sum equal by the following steps:

Count the number of 0s and 1s in the given array arr[] and store them in variables say count_0 and count_1 respectively.
If the sum of the elements at odd and even indices are equal, then no need to remove any array element. Print the original array as the answer.
If count_0 ? N/2, then remove all 1s and print all the zeros count_0 number of times.
Otherwise, if count_0 < N/2, by removing all the 0s, the sum of even and odd indices can be made the same as per the following conditions:
- If count_1 is odd, then print 1 as an element of the new array (count_1 – 1) number of times.
- Otherwise, print 1 as an element of the new array count_1 number of times.
Print the resultant array as per the above conditions.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <iostream>
using namespace std;
 
// Function to modify array to make
// sum of odd and even indexed
// elements equal
void makeArraySumEqual(int a[], int N)
{
   
    // Stores the count of 0s, 1s
    int count_0 = 0, count_1 = 0;
 
    // Stores sum of odd and even
    // indexed elements respectively
    int odd_sum = 0, even_sum = 0;
 
    for (int i = 0; i < N; i++) {
 
        // Count 0s
        if (a[i] == 0)
            count_0++;
 
        // Count 1s
        else
            count_1++;
 
        // Calculate odd_sum and even_sum
        if ((i + 1) % 2 == 0)
            even_sum += a[i];
 
        else if ((i + 1) % 2 > 0)
            odd_sum += a[i];
    }
 
    // If both are equal
    if (odd_sum == even_sum) {
 
        // Print the original array
        for (int i = 0; i < N; i++)
            cout <<" "<< a[i];
    }
 
    // Otherwise
    else {
 
        if (count_0 >= N / 2) {
 
            // Print all the 0s
            for (int i = 0; i < count_0; i++)
                cout <<"0 ";
        }
        else {
 
            // For checking even or odd
            int is_Odd = count_1 % 2;
 
            // Update total count of 1s
            count_1 -= is_Odd;
 
            // Print all 1s
            for (int i = 0; i < count_1; i++)
                cout <<"1 ";
        }
    }
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 1, 1, 1, 0 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    makeArraySumEqual(arr, N);
 
    return 0;
}
 
// This code is contributed by shivanisinghss2110.

C

// C++ program for the above approach
 
#include <stdio.h>
 
// Function to modify array to make
// sum of odd and even indexed
// elements equal
void makeArraySumEqual(int a[], int N)
{
    // Stores the count of 0s, 1s
    int count_0 = 0, count_1 = 0;
 
    // Stores sum of odd and even
    // indexed elements respectively
    int odd_sum = 0, even_sum = 0;
 
    for (int i = 0; i < N; i++) {
 
        // Count 0s
        if (a[i] == 0)
            count_0++;
 
        // Count 1s
        else
            count_1++;
 
        // Calculate odd_sum and even_sum
        if ((i + 1) % 2 == 0)
            even_sum += a[i];
 
        else if ((i + 1) % 2 > 0)
            odd_sum += a[i];
    }
 
    // If both are equal
    if (odd_sum == even_sum) {
 
        // Print the original array
        for (int i = 0; i < N; i++)
            printf("%d ", a[i]);
    }
 
    // Otherwise
    else {
 
        if (count_0 >= N / 2) {
 
            // Print all the 0s
            for (int i = 0; i < count_0; i++)
                printf("0 ");
        }
        else {
 
            // For checking even or odd
            int is_Odd = count_1 % 2;
 
            // Update total count of 1s
            count_1 -= is_Odd;
 
            // Print all 1s
            for (int i = 0; i < count_1; i++)
                printf("1 ");
        }
    }
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 1, 1, 1, 0 };
 
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    makeArraySumEqual(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
 
class GFG {
 
    // Function to modify array to make
    // sum of odd and even indexed
    // elements equal
    static void makeArraySumEqual(int a[], int N)
    {
        // Stores the count of 0s, 1s
        int count_0 = 0, count_1 = 0;
 
        // Stores sum of odd and even
        // indexed elements respectively
        int odd_sum = 0, even_sum = 0;
 
        for (int i = 0; i < N; i++) {
 
            // Count 0s
            if (a[i] == 0)
                count_0++;
 
            // Count 1s
            else
                count_1++;
 
            // Calculate odd_sum and even_sum
            if ((i + 1) % 2 == 0)
                even_sum += a[i];
 
            else if ((i + 1) % 2 > 0)
                odd_sum += a[i];
        }
 
        // If both are equal
        if (odd_sum == even_sum) {
 
            // Print the original array
            for (int i = 0; i < N; i++)
                System.out.print(a[i] + " ");
        }
 
        else
        {
            if (count_0 >= N / 2) {
 
                // Print all the 0s
                for (int i = 0; i < count_0; i++)
                    System.out.print("0 ");
            }
            else {
 
                // For checking even or odd
                int is_Odd = count_1 % 2;
 
                // Update total count of 1s
                count_1 -= is_Odd;
 
                // Print all 1s
                for (int i = 0; i < count_1; i++)
                    System.out.print("1 ");
            }
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given array arr[]
        int arr[] = { 1, 1, 1, 0 };
 
        int N = arr.length;
 
        // Function Call
        makeArraySumEqual(arr, N);
    }
}

Python3

# Python3 program for the above approach 
  
# Function to modify array to make
# sum of odd and even indexed
# elements equal
def makeArraySumEqual(a, N):
     
    # Stores the count of 0s, 1s
    count_0 = 0
    count_1 = 0
  
    # Stores sum of odd and even
    # indexed elements respectively
    odd_sum = 0
    even_sum = 0
  
    for i in range(N):
  
        # Count 0s
        if (a[i] == 0):
            count_0 += 1
  
        # Count 1s
        else:
            count_1 += 1
  
        # Calculate odd_sum and even_sum
        if ((i + 1) % 2 == 0):
            even_sum += a[i]
  
        elif ((i + 1) % 2 > 0):
            odd_sum += a[i]
     
    # If both are equal
    if (odd_sum == even_sum):
  
        # Print the original array
        for i in range(N):
            print(a[i], end = " ")
     
    # Otherwise
    else:
        if (count_0 >= N / 2):
  
            # Print all the 0s
            for i in range(count_0):
                print("0", end = " ")
         
        else:
  
            # For checking even or odd
            is_Odd = count_1 % 2
  
            # Update total count of 1s
            count_1 -= is_Odd
  
            # Print all 1s
            for i in range(count_1):
                print("1", end = " ")
         
# Driver Code
 
# Given array arr[]
arr = [ 1, 1, 1, 0 ]
  
N = len(arr) 
  
# Function call
makeArraySumEqual(arr, N)
 
# This code is contributed by code_hunt

C#

// C# program for 
// the above approach
using System;
class GFG{
 
// Function to modify array to make
// sum of odd and even indexed
// elements equal
static void makeArraySumEqual(int []a, 
                              int N)
{
  // Stores the count of 0s, 1s
  int count_0 = 0, count_1 = 0;
 
  // Stores sum of odd and even
  // indexed elements respectively
  int odd_sum = 0, even_sum = 0;
 
  for (int i = 0; i < N; i++) 
  {
    // Count 0s
    if (a[i] == 0)
      count_0++;
 
    // Count 1s
    else
      count_1++;
 
    // Calculate odd_sum and even_sum
    if ((i + 1) % 2 == 0)
      even_sum += a[i];
 
    else if ((i + 1) % 2 > 0)
      odd_sum += a[i];
  }
 
  // If both are equal
  if (odd_sum == even_sum) 
  {
    // Print the original array
    for (int i = 0; i < N; i++)
      Console.Write(a[i] + " ");
  }
  else
  {
    if (count_0 >= N / 2) 
    {
      // Print all the 0s
      for (int i = 0; i < count_0; i++)
        Console.Write("0 ");
    }
    else
    {
      // For checking even or odd
      int is_Odd = count_1 % 2;
 
      // Update total count of 1s
      count_1 -= is_Odd;
 
      // Print all 1s
      for (int i = 0; i < count_1; i++)
        Console.Write("1 ");
    }
  }
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given array []arr
  int []arr = {1, 1, 1, 0};
 
  int N = arr.Length;
 
  // Function Call
  makeArraySumEqual(arr, N);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
    // Function to modify array to make
    // sum of odd and even indexed
    // elements equal
    function makeArraySumEqual(a, N)
    {
        // Stores the count of 0s, 1s
        let count_0 = 0, count_1 = 0;
  
        // Stores sum of odd and even
        // indexed elements respectively
        let odd_sum = 0, even_sum = 0;
  
        for (let i = 0; i < N; i++) {
  
            // Count 0s
            if (a[i] == 0)
                count_0++;
  
            // Count 1s
            else
                count_1++;
  
            // Calculate odd_sum and even_sum
            if ((i + 1) % 2 == 0)
                even_sum += a[i];
  
            else if ((i + 1) % 2 > 0)
                odd_sum += a[i];
        }
  
        // If both are equal
        if (odd_sum == even_sum) {
  
            // Print the original array
            for (let i = 0; i < N; i++)
                document.write(a[i] + " ");
        }
  
        else
        {
            if (count_0 >= N / 2) {
  
                // Print all the 0s
                for (let i = 0; i < count_0; i++)
                    document.write("0 ");
            }
            else {
  
                // For checking even or odd
                let is_Odd = count_1 % 2;
  
                // Update total count of 1s
                count_1 -= is_Odd;
  
                // Print all 1s
                for (let i = 0; i < count_1; i++)
                    document.write("1 ");
            }
        }
    }
 
// Driver Code
 
    // Given array arr[]
        let arr = [ 1, 1, 1, 0 ];
  
        let N = arr.length;
  
        // Function Call
        makeArraySumEqual(arr, N);
                 
</script>

Output:

1 1

Time Complexity: O(N)
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!