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> |
1 1
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!