Array Indices with Equal sum | Equal Number of Odd or Even numbers on both sides

Problem I

Given an array, find the indices where the sum of numbers on the left equals the sum on the right.

Approach I

This problem could be solved easily using prefix and suffix sums. We’ll calculate the cumulative sum of elements from left to right (prefix or left sum) and store them in a prefix array & similarly will store the cumulative sum of elements from right to left (suffix or right sum) in a suffix array.
After that, we could iterate through the original array to find indices with the same left and right sums ie. index i for which prefixSum[i] == suffixSum[i].
Let’s compute prefixSum[] array and suffixSum[] array.

Prefix Sum Array

Suffix Sum Array

As we could see from the above images,
prefixSum[3] ie. sum a[0..2] = 19
suffixSum[3] ie. sum a[4..5] = 19

Since prefixSum value and suffixSum value is same for index i = 3, this implies that sum[0..2] == sum[4..5]. And hence, i = 3 is the required index.

It is important to note that there could be more than 1, such indices. Also, this implementation assumes prefixSum[0] == 0 && suffixSum[array.size - 1] == 0.

Pseudocode

 findIndicesWithEqualSum(nums):
    n = length(nums)

    # Calculate cumulative prefix sum
    prefixSum[0..n] = 0
    for i = 1 to n:
        prefixSum[i] = prefixSum[i - 1] + nums[i - 1]

    # Calculate cumulative suffix sum
    suffixSum[0..n] = 0
    for i = 1 to n:
        suffixSum[i] = suffixSum[i - 1] + nums[i - 1]

    # Find indices with equal left and right sums
    result = []
    for i = 1 to n:
        if prefixSum[i - 1] == suffixSum[i - 1]:
            result.push(i - 1)

    return result

Code Implementation

//
//  main.cpp
//  Array Equal Sums
//
//  Created by Himanshu on 20/01/24.
//

#include <iostream>
#include <vector>
using namespace std;

vector<int> findIndicesWithEqualSum(const vector<int>& nums) {
    vector<int> result;
    int n = (int) nums.size();
    
    
    // Calculate cumulative prefix sum
    vector<int> prefixSum(n, 0);
    prefixSum[0] = nums[0];
    
    for (int i = 1; i < n; i++) {
        prefixSum[i] = prefixSum[i - 1] + nums[i];
    }
    
    // Calculate cumulative suffix sum
    vector<int> suffixSum(n, 0);
    suffixSum[n-1] = nums[n-1];
    
    for (int i = n-2; i >= 0; i--) {
        suffixSum[i] = suffixSum[i + 1] + nums[i];
    }

    // Find indices with equal left and right sums
    for (int i = 0; i < n; i++) {
        if (prefixSum[i] == suffixSum[i]) {
            result.push_back(i);
        }
    }

    return result;
}

int main() {

    vector<int> nums = {4, 2, -6, 8, -8, 7};
    
    vector<int> result = findIndicesWithEqualSum(nums);

    cout << "Indices with equal left and right sums: " << endl;
    for (int index : result) {
        cout << index << endl;
    }

    return 0;
}

Output

Indices with equal left and right sums: 
5

Time complexity: O(n)
Auxiliary space: O(n)

Approach II

Instead of using prefixSum[] and suffixSum[] arrays, we could use currentPrefixSum and currentSuffixSum int variables to store prefix and suffix sum at the current index i.
After that, we’ll iterate from left to right updating currentPrefixSum and currentSuffixSum variables. And add the index i to the result, where we get currentPrefixSum == currentSuffixSum.

This approach has the advantage of O(1) space complexity

Pseudocode

 findIndicesWithEqualSum(nums):
    n = length(nums)

    #Base case
    if n <= 0:
     return {0}

    # Initialising cumulative prefix sum and suffix sum:
    prefixSum = 0
    suffixSum = 0

    # Calculate cumulative suffix sum
    for i = 0 to n-1:
        suffixSum = suffixSum + nums[i]

    # Find indices with equal left and right sums
    result = []

    for i = 0, j = 1 to n-2:
        // Update prefix and suffix sums
        prefixSum += nums[i];
        suffixSum -= nums[j];

        if prefixSum == suffixSum:
            result.push(i+1)

    return result

Problem II

Given an array, find the indices where the count of odd numbers or the count of even numbers on the left equals the right.

Note: We require the count of even numbers or the count of odd numbers to be equal on both sides. So, the correct solution could have any one of the following conditions met:

• Only the count of odd numbers is equal on both sides.
• Only the count of even numbers is equal on both sides.
• Count of both even numbers and odd numbers is equal on both sides.

Approach

This problem is nothing but a slight variation of the above problem. We could solve it easily by using prefix and suffix arrays of the count of odd numbers and the count of even numbers. We’ll calculate the count of odd elements in the array and the count of even elements in the array from left to right and store them in the prefix odd_array and the prefix even_array respectively. Similarly, we’ll store the count of odd elements in the array and the count of even elements in the array from right to left in the suffix odd_array and the suffix even_array respectively.
Then we could iterate through the original array to find indices with equal count of odd or equal count of even numbers on the left and right.

Let’s compute prefixOdd[] & prefixEven[] arrays and suffixOdd[] & suffixEven[] arrays.

Pseudocode

 findIndicesWithEqualEvenOdd(nums):
    n = length(nums)

    # Calculate count of prefix even & odd numbers
    prefixEven[0..n] = 0
    prefixOdd[0..n] = 0 
    evenNum = 0, oddNum = 0
    for i = 0 to n-2:
        if nums[i] % 2 == 0
            evenNum++
        else
            oddNum++
        prefixEven[i+1] = evenNum, prefixOdd[i+1] = oddNum


    # Calculate count of suffix even & odd numbers
    suffixEven[0..n] = 0
    suffixOdd[0..n] = 0 
    evenNum = 0, oddNum = 0
    for i = n-1 to 1:
        if nums[i] % 2 == 0
            evenNum++
        else
            oddNum++
        suffixEven[i-1] = evenNum, suffixOdd[i-1] = oddNum


    # Find indices with equal count of 
    # odds or evens on both sides
    result = []
    for i = 0 to n-1:
        if prefixEven[i - 1] == suffixEven[i - 1] || 
           prefixOdd[i - 1] == suffixOdd[i - 1]:
            result.push(i - 1)

    return result

Code Implementation

//
//  main.cpp
//  Array Equal Odds or Evens
//
//  Created by Himanshu on 20/01/24.
//


#include <iostream>
#include <vector>
using namespace std;

vector<int> findIndicesWithEqualOddEven(const vector<int>& nums) {
    vector<int> result;
    int n = (int) nums.size();
    int evenNum = 0, oddNum = 0;
    
    
    // Calculate prefix count
    vector<int> prefixEven(n, 0), prefixOdd(n, 0);
    prefixEven[0] = 0;
    prefixOdd[0] = 0;
    
    for (int i = 0; i < n-1; i++) {
        if (nums[i] % 2 == 0) {
            evenNum++;
        } else {
            oddNum++;
        }
        
        prefixEven[i + 1] = evenNum;
        prefixOdd[i + 1] = oddNum;
    }
    

    // Calculate suffix count
    vector<int> suffixEven(n, 0), suffixOdd(n, 0);
    suffixEven[n - 1] = 0;
    suffixOdd[n - 1] = 0;
    evenNum = 0;
    oddNum = 0;
    
    for (int i = n-1; i > 0; i--) {
        if (nums[i] % 2 == 0) {
            evenNum++;
        } else {
            oddNum++;
        }
        
        suffixEven[i - 1] = evenNum;
        suffixOdd[i - 1] = oddNum;
    }
    
    
    // Find indices with equal left and right count of
    // even nums or odd nums
    for (int i = 0; i < n; i++) {
        if ((prefixEven[i] == suffixEven[i]) ||
            (prefixOdd[i] == suffixOdd[i])) {
            
            result.push_back(i);
        }
    }

    return result;
}

int main() {

    vector<int> nums = {3, 4, 5, 2, 2};
    
    vector<int> result = findIndicesWithEqualOddEven(nums);

    cout << "Indices with equal count of odd numbers or even numbers on left and right: " << endl;
    for (int index : result) {
        cout << index << endl;
    }

    return 0;
}

Output

Indices with equal count of odd numbers or even numbers on left and right: 
1
3

Time complexity: O(n)
Auxiliary space: O(n)