Fair Indexes Microsoft OA 2023

Fair Indexes Solution Microsoft OA

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.

For example, given arrays A = [4,-1, 0, 3] and B = [-2, 5, 0, 3], index K = 2 is fair. The sums of the subarrays are all equal: 4+(-1) = 3; 0+3 = 3; -2 + 5 = 3 and 0 + 3 = 3.

Also See: Amazon OA Online Assessment 2023 Questions and Answers

Example

Example 1:

Input: 
[4,-1,0,3] [-2,5,0,3]
Output: 
2

Example 2:

Input: 
[2,-2,-3,3] [0,0,4,-4]
Output: 
1

Example 3:

Input: 
[4,-1,0,3] [-2,6,0,4]
Output: 
0

Example 4:

Input: 
[1,4,2,-2,5] [7,-2,-2,2,5]
Output: 
2

Also See: AMCAT Study Materials, Preparation Guide

SOLUTION

Program Python: Fair Indexes Solution in Python

Solution: prefix sum
Algorithm: Prefix and
Problem-solving ideas
First judge whether the sum of the two arrays are equal, if they are not equal, return 0 directly; then scan the array and use pre_a and pre_b to record the prefix sum of the two arrays respectively. When the prefix sum is equal and equal to the remaining part, ans++ is fine . It should be noted that the value of the number in the array is in the range of -1e9, 1e9, and the length of the array is 0, 1e5, so the middle sum will exceed the int range, and long is required; and the two divided arrays cannot be empty, so the prefix And p0 and pn-1 are not considered;

Complexity analysis
Time complexity: O(n)
Need to traverse the array twice.

Space complexity: O(1)
There is no need to open up additional data space, only a few variables are needed to record the values.

class Solution:
    """
    @param A: an array of integers
    @param B: an array of integers
    @return: return a integer indicating the number of fair indexes.
    """
    def CountIndexes(self, A, B):
        
        if (sum(A) != sum(B)) :
            return 0
        pre_a = 0
        pre_b = 0
        sum_a = sum(A)
        answer = 0
        for i in range(len(A) - 1):
            pre_a = pre_a + A[i]
            pre_b = pre_b + B[i]
            if pre_a == pre_b and pre_a == sum_a - pre_a:
                answer += 1
        return answer

Program Java: Fair Indexes Solution in Java

public class Solution {
    /**
     * @param A: an array of integers
     * @param B: an array of integers
     * @return: return a integer indicating the number of fair indexes.
     */
    public int CountIndexes(List<Integer> A, List<Integer> B) {
        
        int length = A.size();
        long sumA = 0;
        long sumB = 0;
        for (int i = 0; i < length; i++) {
            sumA += A.get(i);
            sumB += B.get(i);
        }
        if (sumA != sumB) {
            return 0;
        }
        long preA = 0, preB = 0;
        int answer = 0;
        for (int i = 0; i < length - 1; i++) {
            preA += A.get(i);
            preB += B.get(i);
            if (preA == preB && sumA - preA == preA) {
                answer += 1;
            }
        }
        
        return answer; 
    }
}

Program C++: Fair Indexes Solution in C++

class Solution {
public:
    /**
     * @param A: an array of integers
     * @param B: an array of integers
     * @return: return a integer indicating the number of fair indexes.
     */
    int CountIndexes(vector<int> &A, vector<int> &B) {
        
        int length = A.size();
        long sumA = 0;
        long sumB = 0;
        for (int i = 0; i < length; i++) {
            sumA += A[i];
            sumB += B[i];
        }
        if (sumA != sumB) {
            return 0;
        }
        long preA = 0, preB = 0;
        int answer = 0;
        for (int i = 0; i < length - 1; i++) {
            preA += A[i];
            preB += B[i];
            if (preA == preB && sumA - preA == preA) {
                answer += 1;
            }
        }
        
        return answer;
    }
};

Microsoft Online Assessment 2023 Questions List

• Maximal Network Rank Solution
• Min Deletions To Obtain String in Right Format
• Day of week that is K days later Solution
• Minimum Adjacent Swaps to Make Palindrome Solution
• Lexicographically Smallest String
• Longest Substring Without Two Contiguous Occurrences of Letter
• String Without 3 Identical Consecutive Letters
• Microsoft OA Longest Semi-Alternating Substring
• Microsoft OA Min Steps to Make Piles Equal Height
• Max Inserts to Obtain String Without 3 Consecutive ‘a’
• Concatenated String Length with unique Characters
• Largest K such that both K and -K exist in array
• Microsoft OA Min Adj Swaps to Group Red Balls
• Maximum Length of a Concatenated String with Unique Characters
• Microsoft OA Unique Integers That Sum Up To 0
• Find N Unique Integers Sum up to Zero
• Microsoft OA Particle Velocity Solution
• Microsoft OA Arithmetic Slices Solution
• Microsoft OA Widest Path Without Trees Solution
• Microsoft OA Jump Game Solution
• Microsoft OA Fair Indexes Solution