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:
int 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
1def fair_indexes(a: list[int], b: list[int]) -> int:
2 # get a prefix sum of each array
3 for i in range(1, len(a)):
4 a[i] += a[i - 1]
5 b[i] += b[i - 1]
6
7 # try each index
8 fair = 0
9 for k in range(1, len(a)):
10 left_a, right_a = a[k - 1], a[-1] - a[k - 1]
11 left_b, right_b = b[k - 1], b[-1] - b[k - 1]
12 fair += int(left_a == right_a == left_b == right_b)
13
14 return fair
15
16if __name__ == "__main__":
17 a = [int(x) for x in input().split()]
18 b = [int(x) for x in input().split()]
19 res = fair_indexes(a, b)
20 print(res)
211import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7 public static int fairIndexes(List<Integer> a, List<Integer> b) {
8 int sumA = 0;
9 int sumB = 0;
10
11 for (int i = 0; i < a.size(); i++) {
12 sumA += a.get(i);
13 sumB += b.get(i);
14 }
15 int count = 0;
16 int tempA = a.get(0);
17 int tempB = b.get(0);
18
19 for (int i = 1; i < a.size(); i++) {
20 if (i != 1 && tempA == tempB && 2 * tempA == sumA && 2 * tempB == sumB) {
21 count++;
22 }
23 tempA += a.get(i);
24 tempB += b.get(i);
25 }
26 return count;
27 }
28
29 public static List<String> splitWords(String s) {
30 return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
31 }
32
33 public static void main(String[] args) {
34 Scanner scanner = new Scanner(System.in);
35 List<Integer> a = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
36 List<Integer> b = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
37 scanner.close();
38 int res = fairIndexes(a, b);
39 System.out.println(res);
40 }
41}
421"use strict";
2
3function fairIndexes(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
23function splitWords(s) {
24 return s === "" ? [] : s.split(" ");
25}
26
27function* main() {
28 const a = splitWords(yield).map((v) => parseInt(v));
29 const b = splitWords(yield).map((v) => parseInt(v));
30 const res = fairIndexes(a, b);
31 console.log(res);
32}
33
34class EOFError extends Error {}
35{
36 const gen = main();
37 const next = (line) => gen.next(line).done && process.exit();
38 let buf = "";
39 next();
40 process.stdin.setEncoding("utf8");
41 process.stdin.on("data", (data) => {
42 const lines = (buf + data).split("\n");
43 buf = lines.pop();
44 lines.forEach(next);
45 });
46 process.stdin.on("end", () => {
47 buf && next(buf);
48 gen.throw(new EOFError());
49 });
50}
51