Equal Odd-Even Sum After Removal

Given an array arr[], count how many indices can be removed such that the sum of elements at even indices equals the sum of elements at odd indices in the resulting array

Examples:

Input: arr[] = [2, 1, 6, 4] 
Output: 1 
Explanation: If we remove the element at index 1 (value 1), the modified array becomes [2, 6, 4]. Now, the sum of elements at even indices (2 + 4 = 6) is equal to the sum at odd indices (6).

Input: arr[] = [1, 1, 1] 
Output: 3 
Explanation: Removing any element makes the sum of left and even indexed elements equal.

[Naive Approach] Using Nested Loop – O(n^2) Time and O(1) Space

The main idea is to simulate the removal of each element and check if the sums of elements at even and odd indices become equal after the shift. By adjusting the index parity during the check, we ensure accuracy without modifying the array.

#include <iostream> #include <vector> using namespace std; int cntWays(vector<int>& arr) {  int n = arr.size();  int res = 0;    // Try removing each element one by one  for (int i = 0; i < n; i++) {  int evenSum = 0, oddSum = 0;  int index = 0;    // Calculate sum of even and odd indexed elements  // after removing element at index i  for (int j = 0; j < n; j++) {    // Skip the removed element  if (j == i) continue;     if (index % 2 == 0) {  evenSum += arr[j];  }   else {  oddSum += arr[j];  }  index++;  }    // Check if even sum equals odd sum  if (evenSum == oddSum) {  res++;  }  }    return res; } int main() {    vector<int> arr = {2, 1, 6, 4};  cout << cntWays(arr);    return 0; } 

class GfG {  static int cntWays(int[] arr) {  int n = arr.length;  int res = 0;    // Try removing each element one by one  for (int i = 0; i < n; i++) {  int evenSum = 0, oddSum = 0;  int index = 0;    // Calculate sum of even and odd indexed elements  // after removing element at index i  for (int j = 0; j < n; j++) {    // Skip the removed element  if (j == i) continue;     if (index % 2 == 0) {  evenSum += arr[j];  }   else {  oddSum += arr[j];  }  index++;  }    // Check if even sum equals odd sum  if (evenSum == oddSum) {  res++;  }  }    return res;  }  public static void main(String[] args) {    int[] arr = {2, 1, 6, 4};  System.out.println(cntWays(arr));    } } 

def cntWays(arr): n = len(arr) res = 0 # Try removing each element one by one for i in range(n): evenSum = 0 oddSum = 0 index = 0 # Calculate sum of even and odd indexed elements # after removing element at index i for j in range(n): # Skip the removed element if j == i: continue if index % 2 == 0: evenSum += arr[j] else: oddSum += arr[j] index += 1 # Check if even sum equals odd sum if evenSum == oddSum: res += 1 return res if __name__ == "__main__": arr = [2, 1, 6, 4] print(cntWays(arr)) 

using System; class GfG {  static int cntWays(int[] arr) {  int n = arr.Length;  int res = 0;    // Try removing each element one by one  for (int i = 0; i < n; i++) {  int evenSum = 0, oddSum = 0;  int index = 0;    // Calculate sum of even and odd indexed elements  // after removing element at index i  for (int j = 0; j < n; j++) {    // Skip the removed element  if (j == i) continue;     if (index % 2 == 0) {  evenSum += arr[j];  }   else {  oddSum += arr[j];  }  index++;  }    // Check if even sum equals odd sum  if (evenSum == oddSum) {  res++;  }  }    return res;  }  static void Main() {  int[] arr = {2, 1, 6, 4};  Console.WriteLine(cntWays(arr));  } } 

function cntWays(arr) {  let n = arr.length;  let res = 0;    // Try removing each element one by one  for (let i = 0; i < n; i++) {  let evenSum = 0, oddSum = 0;  let index = 0;    // Calculate sum of even and odd indexed elements  // after removing element at index i  for (let j = 0; j < n; j++) {    // Skip the removed element  if (j === i) continue;     if (index % 2 === 0) {  evenSum += arr[j];  }   else {  oddSum += arr[j];  }  index++;  }    // Check if even sum equals odd sum  if (evenSum === oddSum) {  res++;  }  }    return res; } // Driver Code let arr = [2, 1, 6, 4]; console.log(cntWays(arr)); 

1

[Expected Approach] Using Prefix and Suffix Sum– O(n) Time and O(1) Space

This optimized approach uses prefix sums to avoid recomputing sums on every removal.
It first calculates the total sum of elements at even and odd indices (right side). Then, as it iterates through the array, it simulates the removal of each element by adjusting the right sums accordingly.
After removal, the indices to the right shift, so the roles of even and odd positions flip.
If the updated left and right sums match (considering the index shift), the index is counted as valid.

Step By Step Implementations:

• Precompute the total sum of even-indexed elements (rightEvenSum) and odd-indexed elements (rightOddSum).
• Initialize leftEvenSum and leftOddSum to 0.
• Iterate through each index i in the array.
• Subtract the current element from the right-side sum based on index parity.
• Since removing the element shifts right-side indices, swap parity when comparing sums.
• Check if leftOddSum + rightEvenSum equals leftEvenSum + rightOddSum.
• If equal, increment the count.
• Add the current element to the left-side sum based on its original parity.

#include <iostream> #include <vector> using namespace std; int cntWays(vector<int>& arr) {  int n = arr.size();  int res = 0;    // Calculate initial right side sums  int rightOddSum = 0, rightEvenSum = 0;  for (int i = 0; i < n; i++) {  if (i % 2 == 0) {  rightEvenSum += arr[i];  }   else {  rightOddSum += arr[i];  }  }    // Initialize left side sums  int leftOddSum = 0, leftEvenSum = 0;    // Check for each index  for (int i = 0; i < n; i++) {    // Remove current element from right side  if (i % 2 == 0) {  rightEvenSum -= arr[i];  }   else {  rightOddSum -= arr[i];  }    // After removing element at index i, indices shift  // So right side odd becomes even and even becomes odd  if (leftOddSum + rightEvenSum ==   leftEvenSum + rightOddSum) {  res++;  }    // Add current element to left side  if (i % 2 == 0) {  leftEvenSum += arr[i];  } else {  leftOddSum += arr[i];  }  }    return res; } int main() {  vector<int> arr = {2, 1, 6, 4};  cout << cntWays(arr);  return 0; } 

class GfG {  static int cntWays(int[] arr) {  int n = arr.length;  int res = 0;    // Calculate initial right side sums  int rightOddSum = 0, rightEvenSum = 0;  for (int i = 0; i < n; i++) {  if (i % 2 == 0) {  rightEvenSum += arr[i];  }   else {  rightOddSum += arr[i];  }  }    // Initialize left side sums  int leftOddSum = 0, leftEvenSum = 0;    // Check for each index  for (int i = 0; i < n; i++) {    // Remove current element from right side  if (i % 2 == 0) {  rightEvenSum -= arr[i];  }   else {  rightOddSum -= arr[i];  }    // After removing element at index i, indices shift  // So right side odd becomes even and even becomes odd  if (leftOddSum + rightEvenSum ==   leftEvenSum + rightOddSum) {  res++;  }    // Add current element to left side  if (i % 2 == 0) {  leftEvenSum += arr[i];  } else {  leftOddSum += arr[i];  }  }    return res;  }  public static void main(String[] args) {  int[] arr = {2, 1, 6, 4};  System.out.println(cntWays(arr));  } } 

def cntWays(arr): n = len(arr) res = 0 # Calculate initial right side sums rightOddSum = 0 rightEvenSum = 0 for i in range(n): if i % 2 == 0: rightEvenSum += arr[i] else: rightOddSum += arr[i] # Initialize left side sums leftOddSum = 0 leftEvenSum = 0 # Check for each index for i in range(n): # Remove current element from right side if i % 2 == 0: rightEvenSum -= arr[i] else: rightOddSum -= arr[i] # After removing element at index i, indices shift # So right side odd becomes even and even becomes odd if leftOddSum + rightEvenSum == \ leftEvenSum + rightOddSum: res += 1 # Add current element to left side if i % 2 == 0: leftEvenSum += arr[i] else: leftOddSum += arr[i] return res if __name__ == "__main__": arr = [2, 1, 6, 4] print(cntWays(arr)) 

using System; class GfG {  static int cntWays(int[] arr) {  int n = arr.Length;  int res = 0;    // Calculate initial right side sums  int rightOddSum = 0, rightEvenSum = 0;  for (int i = 0; i < n; i++) {  if (i % 2 == 0) {  rightEvenSum += arr[i];  }   else {  rightOddSum += arr[i];  }  }    // Initialize left side sums  int leftOddSum = 0, leftEvenSum = 0;    // Check for each index  for (int i = 0; i < n; i++) {    // Remove current element from right side  if (i % 2 == 0) {  rightEvenSum -= arr[i];  }   else {  rightOddSum -= arr[i];  }    // After removing element at index i, indices shift  // So right side odd becomes even and even becomes odd  if (leftOddSum + rightEvenSum ==   leftEvenSum + rightOddSum) {  res++;  }    // Add current element to left side  if (i % 2 == 0) {  leftEvenSum += arr[i];  } else {  leftOddSum += arr[i];  }  }    return res;  }  static void Main() {  int[] arr = {2, 1, 6, 4};  Console.WriteLine(cntWays(arr));  } } 

function cntWays(arr) {  let n = arr.length;  let res = 0;    // Calculate initial right side sums  let rightOddSum = 0, rightEvenSum = 0;  for (let i = 0; i < n; i++) {  if (i % 2 === 0) {  rightEvenSum += arr[i];  }   else {  rightOddSum += arr[i];  }  }    // Initialize left side sums  let leftOddSum = 0, leftEvenSum = 0;    // Check for each index  for (let i = 0; i < n; i++) {    // Remove current element from right side  if (i % 2 === 0) {  rightEvenSum -= arr[i];  }   else {  rightOddSum -= arr[i];  }    // After removing element at index i, indices shift  // So right side odd becomes even and even becomes odd  if (leftOddSum + rightEvenSum ===   leftEvenSum + rightOddSum) {  res++;  }    // Add current element to left side  if (i % 2 === 0) {  leftEvenSum += arr[i];  } else {  leftOddSum += arr[i];  }  }    return res; } // Driver Code let arr = [2, 1, 6, 4]; console.log(cntWays(arr)); 

1

18bhupenderyadav18

Follow