# Fair Indexes Microsoft OA 2023

## Fair Indexes Solution Microsoft OA

You are given two arrays A and B consisting of N integers each.

Index K is named fair if the four sums(A+…A[K-1]),(A[K]+…+A[N-1]),(B+…+B[K-1]) and (B[K]+…+B[N-1]) are all equal, In other words, K is the index where the two arrays, A and B, can be split (into two non-empty arrays each) in such a way that the sums of the resulting arrays’ elements are equal.

For example, given arrays A = [4,-1, 0, 3] and B = [-2, 5, 0, 3], index K = 2 is fair. The sums of the subarrays are all equal: 4+(-1) = 3; 0+3 = 3; -2 + 5 = 3 and 0 + 3 = 3.

Also See: Amazon OA Online Assessment 2023 Questions and Answers

Example

Example 1:

``````Input:
[4,-1,0,3] [-2,5,0,3]
Output:
2``````

Example 2:

``````Input:
[2,-2,-3,3] [0,0,4,-4]
Output:
1``````

Example 3:

``````Input:
[4,-1,0,3] [-2,6,0,4]
Output:
0``````

Example 4:

``````Input:
[1,4,2,-2,5] [7,-2,-2,2,5]
Output:
2``````

Also See: AMCAT Study Materials, Preparation Guide

### SOLUTION

Program Python: Fair Indexes Solution in Python

Solution: prefix sum
Algorithm: Prefix and
Problem-solving ideas

First judge whether the sum of the two arrays are equal, if they are not equal, return 0 directly; then scan the array and use pre_a and pre_b to record the prefix sum of the two arrays respectively. When the prefix sum is equal and equal to the remaining part, ans++ is fine . It should be noted that the value of the number in the array is in the range of -1e9, 1e9, and the length of the array is 0, 1e5, so the middle sum will exceed the int range, and long is required; and the two divided arrays cannot be empty, so the prefix And p0 and pn-1 are not considered;

Complexity analysis
Time complexity: O(n)
Need to traverse the array twice.

Space complexity: O(1)
There is no need to open up additional data space, only a few variables are needed to record the values.

``````class Solution:
"""
@param A: an array of integers
@param B: an array of integers
@return: return a integer indicating the number of fair indexes.
"""
def CountIndexes(self, A, B):

if (sum(A) != sum(B)) :
return 0
pre_a = 0
pre_b = 0
sum_a = sum(A)
for i in range(len(A) - 1):
pre_a = pre_a + A[i]
pre_b = pre_b + B[i]
if pre_a == pre_b and pre_a == sum_a - pre_a:

Program Java: Fair Indexes Solution in Java

``````public class Solution {
/**
* @param A: an array of integers
* @param B: an array of integers
* @return: return a integer indicating the number of fair indexes.
*/
public int CountIndexes(List<Integer> A, List<Integer> B) {

int length = A.size();
long sumA = 0;
long sumB = 0;
for (int i = 0; i < length; i++) {
sumA += A.get(i);
sumB += B.get(i);
}
if (sumA != sumB) {
return 0;
}
long preA = 0, preB = 0;
for (int i = 0; i < length - 1; i++) {
preA += A.get(i);
preB += B.get(i);
if (preA == preB && sumA - preA == preA) {
}
}

}
}``````

Program C++: Fair Indexes Solution in C++

``````class Solution {
public:
/**
* @param A: an array of integers
* @param B: an array of integers
* @return: return a integer indicating the number of fair indexes.
*/
int CountIndexes(vector<int> &A, vector<int> &B) {

int length = A.size();
long sumA = 0;
long sumB = 0;
for (int i = 0; i < length; i++) {
sumA += A[i];
sumB += B[i];
}
if (sumA != sumB) {
return 0;
}
long preA = 0, preB = 0;