# 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)