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 indices are 2 and 3. In both cases, the sums of elements in 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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫