Count ways to make sum of odd and even indexed elements equal by removing an array element
Given an array, arr[] of size N, the task is to find the count of array indices such that removing an element from these indices makes the sum of even-indexed and odd-indexed array elements equal.
Examples:
Input: arr[] = { 2, 1, 6, 4 }
Output: 1
Explanation:
Removing arr[1] from the array modifies arr[] to { 2, 6, 4 } such that, arr[0] + arr[2] = arr[1].
Therefore, the required output is 1.Input: arr[] = { 1, 1, 1 }
Output: 3
Explanation:
Removing arr[0] from the given array modifies arr[] to { 1, 1 } such that arr[0] = arr[1]
Removing arr[1] from the given array modifies arr[] to { 1, 1 } such that arr[0] = arr[1]
Removing arr[2] from the given array modifies arr[] to { 1, 1 } such that arr[0] = arr[1]
Therefore, the required output is 3.
Naive Approach: The simplest approach to solve this problem is to traverse the array and for each array element, check if removing the element from the array makes the sum of even-indexed and odd-indexed array elements equal or not. If found to be true, then increment the count. Finally, print the count.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the observation that removing any element from the given array makes even indices of succeeding elements as odd and odd indices of the succeeding elements as even. Follow the steps below to solve the problem:
- Initialize two variables, say evenSum and oddSum, to store the sum of odd-indexed and even-indexed elements of the given array respectively.
- Traverse the array using variable i.
- Remove every ith element of the array and update the sum of the remaining even-indexed elements and the odd-indexed elements based on the above observation. Check if the sums are equal or not. If found to be true, then increment the count.
- Finally, print the count obtained.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to count array indices // whose removal makes sum of odd and // even indexed elements equal int cntIndexesToMakeBalance( int arr[], int n) { // If size of the array is 1 if (n == 1) { return 1; } // If size of the array is 2 if (n == 2) return 0; // Stores sum of even-indexed // elements of the given array int sumEven = 0; // Stores sum of odd-indexed // elements of the given array int sumOdd = 0; // Traverse the array for ( int i = 0; i < n; i++) { // If i is an even number if (i % 2 == 0) { // Update sumEven sumEven += arr[i]; } // If i is an odd number else { // Update sumOdd sumOdd += arr[i]; } } // Stores sum of even-indexed // array elements till i-th index int currOdd = 0; // Stores sum of odd-indexed // array elements till i-th index int currEven = arr[0]; // Stores count of indices whose // removal makes sum of odd and // even indexed elements equal int res = 0; // Stores sum of even-indexed elements // after removing the i-th element int newEvenSum = 0; // Stores sum of odd-indexed elements // after removing the i-th element int newOddSum = 0; // Traverse the array for ( int i = 1; i < n - 1; i++) { // If i is an odd number if (i % 2) { // Update currOdd currOdd += arr[i]; // Update newEvenSum newEvenSum = currEven + sumOdd - currOdd; // Update newOddSum newOddSum = currOdd + sumEven - currEven - arr[i]; } // If i is an even number else { // Update currEven currEven += arr[i]; // Update newOddSum newOddSum = currOdd + sumEven - currEven; // Update newEvenSum newEvenSum = currEven + sumOdd - currOdd - arr[i]; } // If newEvenSum is equal to newOddSum if (newEvenSum == newOddSum) { // Increase the count res++; } } // If sum of even-indexed and odd-indexed // elements is equal by removing the first element if (sumOdd == sumEven - arr[0]) { // Increase the count res++; } // If length of the array // is an odd number if (n % 2 == 1) { // If sum of even-indexed and odd-indexed // elements is equal by removing the last element if (sumOdd == sumEven - arr[n - 1]) { // Increase the count res++; } } // If length of the array // is an even number else { // If sum of even-indexed and odd-indexed // elements is equal by removing the last element if (sumEven == sumOdd - arr[n - 1]) { // Increase the count res++; } } return res; } // Driver Code int main() { int arr[] = { 1, 1, 1 }; int n = sizeof (arr) / sizeof (arr[0]); cout << cntIndexesToMakeBalance(arr, n); return 0; } |
Java
// Java program to implement // the above approach class GFG { // Function to count array indices // whose removal makes sum of odd and // even indexed elements equal static int cntIndexesToMakeBalance( int arr[], int n) { // If size of the array is 1 if (n == 1 ) { return 1 ; } // If size of the array is 2 if (n == 2 ) return 0 ; // Stores sum of even-indexed // elements of the given array int sumEven = 0 ; // Stores sum of odd-indexed // elements of the given array int sumOdd = 0 ; // Traverse the array for ( int i = 0 ; i < n; i++) { // If i is an even number if (i % 2 == 0 ) { // Update sumEven sumEven += arr[i]; } // If i is an odd number else { // Update sumOdd sumOdd += arr[i]; } } // Stores sum of even-indexed // array elements till i-th index int currOdd = 0 ; // Stores sum of odd-indexed // array elements till i-th index int currEven = arr[ 0 ]; // Stores count of indices whose // removal makes sum of odd and // even indexed elements equal int res = 0 ; // Stores sum of even-indexed elements // after removing the i-th element int newEvenSum = 0 ; // Stores sum of odd-indexed elements // after removing the i-th element int newOddSum = 0 ; // Traverse the array for ( int i = 1 ; i < n - 1 ; i++) { // If i is an odd number if (i % 2 != 0 ) { // Update currOdd currOdd += arr[i]; // Update newEvenSum newEvenSum = currEven + sumOdd - currOdd; // Update newOddSum newOddSum = currOdd + sumEven - currEven - arr[i]; } // If i is an even number else { // Update currEven currEven += arr[i]; // Update newOddSum newOddSum = currOdd + sumEven - currEven; // Update newEvenSum newEvenSum = currEven + sumOdd - currOdd - arr[i]; } // If newEvenSum is equal to newOddSum if (newEvenSum == newOddSum) { // Increase the count res++; } } // If sum of even-indexed and odd-indexed // elements is equal by removing the first element if (sumOdd == sumEven - arr[ 0 ]) { // Increase the count res++; } // If length of the array // is an odd number if (n % 2 == 1 ) { // If sum of even-indexed and odd-indexed // elements is equal by removing the last element if (sumOdd == sumEven - arr[n - 1 ]) { // Increase the count res++; } } // If length of the array // is an even number else { // If sum of even-indexed and odd-indexed // elements is equal by removing the last element if (sumEven == sumOdd - arr[n - 1 ]) { // Increase the count res++; } } return res; } // Driver Code public static void main (String[] args) { int arr[] = { 1 , 1 , 1 }; int n = arr.length; System.out.println(cntIndexesToMakeBalance(arr, n)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 program to implement # the above approach # Function to count array indices # whose removal makes sum of odd and # even indexed elements equal def cntIndexesToMakeBalance(arr, n): # If size of the array is 1 if (n = = 1 ): return 1 # If size of the array is 2 if (n = = 2 ): return 0 # Stores sum of even-indexed # elements of the given array sumEven = 0 # Stores sum of odd-indexed # elements of the given array sumOdd = 0 # Traverse the array for i in range (n): # If i is an even number if (i % 2 = = 0 ): # Update sumEven sumEven + = arr[i] # If i is an odd number else : # Update sumOdd sumOdd + = arr[i] # Stores sum of even-indexed # array elements till i-th index currOdd = 0 # Stores sum of odd-indexed # array elements till i-th index currEven = arr[ 0 ] # Stores count of indices whose # removal makes sum of odd and # even indexed elements equal res = 0 # Stores sum of even-indexed elements # after removing the i-th element newEvenSum = 0 # Stores sum of odd-indexed elements # after removing the i-th element newOddSum = 0 # Traverse the array for i in range ( 1 , n - 1 ): # If i is an odd number if (i % 2 ): # Update currOdd currOdd + = arr[i] # Update newEvenSum newEvenSum = (currEven + sumOdd - currOdd) # Update newOddSum newOddSum = (currOdd + sumEven - currEven - arr[i]) # If i is an even number else : # Update currEven currEven + = arr[i] # Update newOddSum newOddSum = (currOdd + sumEven - currEven) # Update newEvenSum newEvenSum = (currEven + sumOdd - currOdd - arr[i]) # If newEvenSum is equal to newOddSum if (newEvenSum = = newOddSum): # Increase the count res + = 1 # If sum of even-indexed and odd-indexed # elements is equal by removing the first # element if (sumOdd = = sumEven - arr[ 0 ]): # Increase the count res + = 1 # If length of the array # is an odd number if (n % 2 = = 1 ): # If sum of even-indexed and odd-indexed # elements is equal by removing the last # element if (sumOdd = = sumEven - arr[n - 1 ]): # Increase the count res + = 1 # If length of the array # is an even number else : # If sum of even-indexed and odd-indexed # elements is equal by removing the last # element if (sumEven = = sumOdd - arr[n - 1 ]): # Increase the count res + = 1 return res # Driver Code if __name__ = = "__main__" : arr = [ 1 , 1 , 1 ] n = len (arr) print (cntIndexesToMakeBalance(arr, n)) # This code is contributed by AnkitRai01 |
C#
// C# program to implement // the above approach using System; class GFG { // Function to count array indices // whose removal makes sum of odd and // even indexed elements equal static int cntIndexesToMakeBalance( int [] arr, int n) { // If size of the array is 1 if (n == 1) { return 1; } // If size of the array is 2 if (n == 2) return 0; // Stores sum of even-indexed // elements of the given array int sumEven = 0; // Stores sum of odd-indexed // elements of the given array int sumOdd = 0; // Traverse the array for ( int i = 0; i < n; i++) { // If i is an even number if (i % 2 == 0) { // Update sumEven sumEven += arr[i]; } // If i is an odd number else { // Update sumOdd sumOdd += arr[i]; } } // Stores sum of even-indexed // array elements till i-th index int currOdd = 0; // Stores sum of odd-indexed // array elements till i-th index int currEven = arr[0]; // Stores count of indices whose // removal makes sum of odd and // even indexed elements equal int res = 0; // Stores sum of even-indexed elements // after removing the i-th element int newEvenSum = 0; // Stores sum of odd-indexed elements // after removing the i-th element int newOddSum = 0; // Traverse the array for ( int i = 1; i < n - 1; i++) { // If i is an odd number if (i % 2 != 0) { // Update currOdd currOdd += arr[i]; // Update newEvenSum newEvenSum = currEven + sumOdd - currOdd; // Update newOddSum newOddSum = currOdd + sumEven - currEven - arr[i]; } // If i is an even number else { // Update currEven currEven += arr[i]; // Update newOddSum newOddSum = currOdd + sumEven - currEven; // Update newEvenSum newEvenSum = currEven + sumOdd - currOdd - arr[i]; } // If newEvenSum is equal to newOddSum if (newEvenSum == newOddSum) { // Increase the count res++; } } // If sum of even-indexed and odd-indexed // elements is equal by removing the first element if (sumOdd == sumEven - arr[0]) { // Increase the count res++; } // If length of the array // is an odd number if (n % 2 == 1) { // If sum of even-indexed and odd-indexed // elements is equal by removing the last element if (sumOdd == sumEven - arr[n - 1]) { // Increase the count res++; } } // If length of the array // is an even number else { // If sum of even-indexed and odd-indexed // elements is equal by removing the last element if (sumEven == sumOdd - arr[n - 1]) { // Increase the count res++; } } return res; } // Drivers Code public static void Main () { int [] arr = { 1, 1, 1 }; int n = arr.Length; Console.WriteLine(cntIndexesToMakeBalance(arr, n)); } } // This code is contributed by susmitakundugoaldanga |
Javascript
<script> // Javascript program to implement // the above approach // Function to count array indices // whose removal makes sum of odd and // even indexed elements equal function cntIndexesToMakeBalance(arr, n) { // If size of the array is 1 if (n == 1) { return 1; } // If size of the array is 2 if (n == 2) return 0; // Stores sum of even-indexed // elements of the given array let sumEven = 0; // Stores sum of odd-indexed // elements of the given array let sumOdd = 0; // Traverse the array for (let i = 0; i < n; i++) { // If i is an even number if (i % 2 == 0) { // Update sumEven sumEven += arr[i]; } // If i is an odd number else { // Update sumOdd sumOdd += arr[i]; } } // Stores sum of even-indexed // array elements till i-th index let currOdd = 0; // Stores sum of odd-indexed // array elements till i-th index let currEven = arr[0]; // Stores count of indices whose // removal makes sum of odd and // even indexed elements equal let res = 0; // Stores sum of even-indexed elements // after removing the i-th element let newEvenSum = 0; // Stores sum of odd-indexed elements // after removing the i-th element let newOddSum = 0; // Traverse the array for (let i = 1; i < n - 1; i++) { // If i is an odd number if (i % 2) { // Update currOdd currOdd += arr[i]; // Update newEvenSum newEvenSum = currEven + sumOdd - currOdd; // Update newOddSum newOddSum = currOdd + sumEven - currEven - arr[i]; } // If i is an even number else { // Update currEven currEven += arr[i]; // Update newOddSum newOddSum = currOdd + sumEven - currEven; // Update newEvenSum newEvenSum = currEven + sumOdd - currOdd - arr[i]; } // If newEvenSum is equal to newOddSum if (newEvenSum == newOddSum) { // Increase the count res++; } } // If sum of even-indexed and odd-indexed // elements is equal by removing the first element if (sumOdd == sumEven - arr[0]) { // Increase the count res++; } // If length of the array // is an odd number if (n % 2 == 1) { // If sum of even-indexed and odd-indexed // elements is equal by removing the last element if (sumOdd == sumEven - arr[n - 1]) { // Increase the count res++; } } // If length of the array // is an even number else { // If sum of even-indexed and odd-indexed // elements is equal by removing the last element if (sumEven == sumOdd - arr[n - 1]) { // Increase the count res++; } } return res; } // Driver Code let arr = [ 1, 1, 1 ]; let n = arr.length; document.write(cntIndexesToMakeBalance(arr, n)); // This code is contributed by Mayank Tyagi </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)