Last Updated: 23 Aug, 2021
Fair Indexes
Moderate
Asked in companies
Levi Ackerman has two arrays, ‘A’ and ‘B’ consisting of ‘N’ integers each. He wants to divide these two arrays into two parts each, such that the sum of all the elements in the first part is equal to the sum of elements in the second part, and the index ‘k’ where the splitting is done, must be the same in both the arrays.
In simple terms, If he splits the array at index k, then (A[0]+A[1]....A[k]), (A[k + 1] + A[k + 2]....A[n - 1]), (B[0] + B[1]....B[k]), (B[k + 1] + B[k + 2]....B[n - 1]) are all equal.
Find the total number of all the Indexes which satisfy the given condition.
For Example :
n = 4, A = {2, 4, 5, 1}, B = {3, 3, 10, -4}
Now in this example, if we split the array at index 1 then the sum of all the subarrays is 2 + 4 = 6, 5 + 1 = 6, 3 + 3 = 6, 10 + (-4) = 6, and no other index satisfies this condition, hence the answer is 1.
Input Format :
The first line of input format contains ‘T’, denoting the number of test cases. Then each test case follows.
The first line of each test case contains an integer ‘n’, Denoting the number of elements in the array A and B.
The second line of the test case contains an array of ‘n’ integers denoting the elements of array A.
The third line of the test case contains an array of ‘n’ integers denoting the elements of array B.
Output Format :
For each test case, print a single integer “ans” denoting the maximum number of indexes satisfying the given condition.
Output for every query will be printed in a separate line.
Note :
You are not required to print anything explicitly. It has already been taken care of. Just implement the functions.
Constraints :
1 <= T <= 100
2 <= N <= 10^5
-10^9 <= A[i], B[i] <= 10^9
Time Limit: 1 second
Approaches
The approach is simple:
Start from the first element of the array till the last element of the array and check whether the sum of first i numbers equals the sum of the last n-i numbers for both the arrays.
The steps are as following:
- Take a variable “count”, which will store the count of all the indexes satisfying the given condition.
- Find the sum of all elements of ‘A’ and ‘B’ and store them in “finalsum1” and “finalsum2”.
- Iterate through the array from 0 to n - 1(say iterator be i):
- Take two variables, “sum1” and “sum2”, and iterate through both the arrays ‘A’ and ‘B’ from 0 to i (say iterator be j):
- Add “A[j]” to “sum1” and “B[j]” to “sum2”.
- If “sum1” equals to “sum2” and 2 * “sum1” = “finalsum1” and 2 * “sum2” = “finalsum2” increment the value of “count” by 1.
- Take two variables, “sum1” and “sum2”, and iterate through both the arrays ‘A’ and ‘B’ from 0 to i (say iterator be j):
- Return “count”.
In this approach, we will iterate through the array of strings and precompute the values of each index of array A and B and then iterate in the array to check the sum of all the indexes.
The steps are as following:
- Take a variable “count”, which will store the count of all the indexes satisfying the given condition.
- Find the prefix sum of all elements of ‘A’ and ‘B’ and store them in an array “prefA” and “prefB”, respectively.
- Iterate through the array from 0 to n - 1(say iterator be i):
- Check whether the “prefA[i]” equals to “prefB[i]” and “prefA[n - 1]” = 2 * “prefA[i]” and “prefB[n - 1]” = 2 * “prefB[i]”.
- If the condition is valid, increment “count” by 1.
- Return “count”.
Similar problems