Microsoft OA Fair Indexes Solution

Microsoft OA Fair Indexes Solution

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.

Also See: Microsoft Online Assessment Questions and Solution

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 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.

Solution:

Program Python:

from typing import List
from collections import deque
def fairIndexes(A: List[int], B: List[int]) -> int:
    for i in range(1, len(A)):
        A[i] += A[i - 1]
        B[i] += B[i - 1]
    fair = 0
    for k in range(1, len(A)):
        left_A, right_A = A[k - 1], A[-1] - A[k - 1]
        left_B, right_B = B[k - 1], B[-1] - B[k - 1]
        fair += int(left_A == right_A == left_B == right_B)
    return fair
if __name__ == '__main__':
      A = [int(x) for x in input().split()]
      B = [int(y) for y in input().split()]
      print(fairIndexes(A, B))

Program Java:

import java.io.IOException;
import java.util.*;
class Solution {
     public static int fairIndex(int a[], int b[]){
        int sumA = 0;
        int sumB = 0;
        for (int i = 0; i < a.length; i++) {
            sumA += a[i];
            sumB += b[i];
        }
        int count = 0;
        int tempA = a[0];
        int tempB = b[0];
        for (int i = 1; i < a.length; i++) {
            if (i != 1 && tempA == tempB && 2 * tempA == sumA && 2 * tempB == sumB) {
                count++;
            }
            tempA += a[i];
            tempB += b[i];
        }
        return count;
    }
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int[] A1 = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] B1 = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        System.out.println(fairIndex(A1, B1));
    }
}

Program JavaScript:

const readline = require('readline');
function fairIndex(a, b) {
    let sumA = 0;
    let sumB = 0;
    for (let i = 0; i < a.length; i++) {
        sumA += a[i];
        sumB += b[i];
    }
    let count = 0;
    let tempA = a[0];
    let tempB = b[0];
    for (let j = 1; j < a.length; j++) {
        if (j !== 1 && tempA === tempB && 2 * tempA === sumA && 2 * tempB == sumB) {
            count++;
        }
        tempA += a[j];
        tempB += b[j];
    }
    return count;
}
const rl = readline.createInterface(process.stdin);
const inputs = [];
rl.on('line', (input) => {
    input !== '' ? inputs.push(input) : rl.close();
}).on('close', () => {
    const a = inputs[0].split(" ").map(Number => parseInt(Number));
    const b = inputs[1].split(" ").map(Number => parseInt(Number));
    rl.close();
    console.log(fairIndex(a, b));
});

Also See: AMCAT Study Materials, Preparation Guide

Also See: Amazon OA 2021 (Online Assessment) Questions Preparation

Microsoft Online Assessment 2021 Questions

Leave a Comment