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
1import java.io.IOException;
2import java.util.*;
3
4class Solution {
5
6 public static int fairIndex(int a[], int b[]){
7 int sumA = 0;
8 int sumB = 0;
9
10 for (int i = 0; i < a.length; i++) {
11 sumA += a[i];
12 sumB += b[i];
13 }
14 int count = 0;
15 int tempA = a[0];
16 int tempB = b[0];
17
18 for (int i = 1; i < a.length; i++) {
19 if (i != 1 && tempA == tempB && 2 * tempA == sumA && 2 * tempB == sumB) {
20 count++;
21 }
22 tempA += a[i];
23 tempB += b[i];
24 }
25 return count;
26 }
27
28 public static void main(String[] args) throws IOException {
29 Scanner scanner = new Scanner(System.in);
30 int[] A1 = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
31 int[] B1 = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
32 System.out.println(fairIndex(A1, B1));
33 }
34
35}
36
1const readline = require('readline');
2
3function fairIndex(a, b) {
4 let sumA = 0;
5 let sumB = 0;
6 for (let i = 0; i < a.length; i++) {
7 sumA += a[i];
8 sumB += b[i];
9 }
10 let count = 0;
11 let tempA = a[0];
12 let tempB = b[0];
13 for (let j = 1; j < a.length; j++) {
14 if (j !== 1 && tempA === tempB && 2 * tempA === sumA && 2 * tempB == sumB) {
15 count++;
16 }
17 tempA += a[j];
18 tempB += b[j];
19 }
20 return count;
21}
22
23const rl = readline.createInterface(process.stdin);
24const inputs = [];
25rl.on('line', (input) => {
26 input !== '' ? inputs.push(input) : rl.close();
27}).on('close', () => {
28 const a = inputs[0].split(" ").map(Number => parseInt(Number));
29 const b = inputs[1].split(" ").map(Number => parseInt(Number));
30 rl.close();
31 console.log(fairIndex(a, b));
32});
33
Still not clear? Submit the part you don't understand to our editors.