Fair Indexes

Moderate
0/80
profile
Contributed by
16 upvotes
Asked in companies
SAP LabsMicrosoftHashedIn

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
1 2 3
2 1 3
2
6 6
10 2
Sample Output 1 :
1
0
Explanation For Sample Output 1 :
In the first test case, at index 1, the sum of the first array is 3, 3, and the sum of the second array is also 3, 3. Hence the answer is 1.

 In the second test case, There is no index satisfying the given condition. Hence, the answer is 0.
Sample Input 2 :
2
5
-5 2 -10 -3 6
-5 -10 3 4 -2
5  
1 4 2 -2 5 
7 -2 -2 2 5
Sample Output 2 :
1
2
Hint

Check the sum for every index of the array

Approaches (2)
Naive Approach

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.
  • Return “count”.
Time Complexity

O(N ^ 2). Where N is the total number of elements in the array.

 

Since we are iterating in the array in a nested loop. 

Hence, the time complexity is O(N ^ 2).

Space Complexity

O( 1 ).

 

Since we are not using any auxiliary space. 

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Fair Indexes
Full screen
Console