Microsoft Online Assessment (OA) - Fair Indexes
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.
write a function:
1int fairIndexes(vector<int> &A, vector<int> &B);
which, given two arrays of integers A and B, returns the number of fair indexes.
Example 1:
Input: A = [4, -1, 0, 3], B = [-2, 5, 0, 3]
Output: 2
Explanation:
The fair indexes are 2 and 3. In both cases, the sums of elements the subarrays are equal to 3.
For index = 2;
4 + (-1) = 3; 0 + 3 = 3;
-2 + 5 = 3; 0 + 3 = 3;
Example 2:
Input: A = [2, -2, -3, 3], B = [0, 0, 4, -4]
Output: 1
Explanation:
The only fair index is 2.
Try it yourself
Implementation
1from typing import List
2from collections import deque
3
4def fairIndexes(A: List[int], B: List[int]) -> int:
5 # GET A PREFIX SUM OF EACH ARRAY
6 for i in range(1, len(A)):
7 A[i] += A[i - 1]
8 B[i] += B[i - 1]
9
10 # TRY EACH INDEX
11 fair = 0
12 for k in range(1, len(A)):
13 left_A, right_A = A[k - 1], A[-1] - A[k - 1]
14 left_B, right_B = B[k - 1], B[-1] - B[k - 1]
15 fair += int(left_A == right_A == left_B == right_B)
16
17 return fair
18if __name__ == '__main__':
19 A = [int(x) for x in input().split()]
20 B = [int(y) for y in input().split()]
21 print(fairIndexes(A, B))
22
23