Contents
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