Contents

**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[0]+…A[K-1]),(A[K]+…+A[N-1]),(B[0]+…+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 sumAlgorithm: Prefix andProblem-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)
answer = 0
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:
answer += 1
return answer
```

*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;
int answer = 0;
for (int i = 0; i < length - 1; i++) {
preA += A.get(i);
preB += B.get(i);
if (preA == preB && sumA - preA == preA) {
answer += 1;
}
}
return answer;
}
}
```

*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;
int answer = 0;
for (int i = 0; i < length - 1; i++) {
preA += A[i];
preB += B[i];
if (preA == preB && sumA - preA == preA) {
answer += 1;
}
}
return answer;
}
};
```

**Microsoft Online Assessment 2023 Questions List**

*Maximal Network Rank Solution**Min Deletions To Obtain String in Right Format**Day of week that is K days later Solution**Minimum Adjacent Swaps to Make Palindrome Solution**Lexicographically Smallest String**Longest Substring Without Two Contiguous Occurrences of Letter**String Without 3 Identical Consecutive Letters**Microsoft OA Longest Semi-Alternating Substring**Microsoft OA Min Steps to Make Piles Equal Height**Max Inserts to Obtain String Without 3 Consecutive ‘a’**Concatenated String Length with unique Characters**Largest K such that both K and -K exist in array**Microsoft OA Min Adj Swaps to Group Red Balls**Maximum Length of a Concatenated String with Unique Characters**Microsoft OA Unique Integers That Sum Up To 0**Find N Unique Integers Sum up to Zero**Microsoft OA Particle Velocity Solution**Microsoft OA Arithmetic Slices Solution**Microsoft OA Widest Path Without Trees Solution**Microsoft OA Jump Game Solution**Microsoft OA Fair Indexes Solution*