Equal Arrays

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
10 upvotes
Asked in company
Prodapt Solutions

Problem statement

You are given two arrays 'A' and 'B' of length 'N' and 'M' respectively. You can perform the following operation any number of times on 'A' and 'B'.

1. Replace any subarray of the array with the sum of the elements in the subarray. For example :- If we have an array 'A' = [2, 3, 5, 6, 1], then we can replace the subarray from index 1 to index 3 (0-based indexing) i.e. [3, 5, 6] with its sum i.e. 3 + 5 + 6 = 14 to get 'A' =  [2, 14, 1].

You want to make 'A' and 'B' equal. Return the maximum possible length of arrays 'A' and 'B' such that 'A' is equal to 'B'. If it is impossible to make 'A' and 'B' equal then return -1.

A subarray is a contiguous part of the array.

For Example:-
Let 'N' = 4, 'M' = 5, 'A' = [2, 1, 4, 3], 'B' = [2, 5, 1, 1, 1].
 We can perform operations on 'A' from index 2 to 3 and on 'B' from index 3 to 5 (1-based indexing).
'A' and 'B' after performing the operation is [2, 5, 3].
The maximum possible length is 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format:-
First-line contains an integer 'T', which denotes the number of test cases.
For every test case:-
First-line contains two integers 'N' and 'M', denoting the length of the array 'A' and 'B'.
Second-line contains 'N' space-separated integers, elements of array 'A'.
Third-line contains 'M' space-separated integers, elements of array 'B'.
Output Format:-
For each test case, Return the maximum possible length of arrays 'A' and 'B' such that 'A' is equal to 'B'. If it is impossible to make 'A' and 'B' equal then return -1.
Note:-
You don’t need to print anything. Just implement the given function.
Constraints:-
1 <= 'T' <= 10
1 <= 'N','M' <= 10^5
1 <= 'A[i]', 'B[i]' <= 10^5

The Sum of 'N' overall test cases does not exceed 10^5.
Time Limit: 1 sec
Sample Input 1:-
2
3 4
3 2 2
1 3 1 3
5 3
1 3 2 2 3
4 2 5
Sample Output 1:-
-1
3
Explanation of sample input 1:-
First test case:-
It can be proven that we cannot make 'A' and 'B' equal.
So our answer is -1.

Second test case:-
We can perform operations on 'A' from index 1 to 2 and from index 4 to 5 (1-based indexing).
'A' and 'B' after performing the operation is [4, 2, 5].
The maximum possible length is 3.
Sample Input 2:-
2
5 2
3 2 5 1 6
4 7 
4 4
4 3 2 1
1 2 3 4
Sample Output 2:-
 -1
 1
Hint

How does comparing the sum of the arrays help?

Approaches (1)
Greedy, Two-Pointers

Approach:-

 

  • If the sum of the two arrays is not equal:
    • Then we cannot make 'A' and B' equal.
  • Otherwise:
    • Now we have to find the maximum possible length, for that, we have to perform the minimum operations on 'A' and 'B'.
    • We combine the segments of 'A' and of 'B' until the segments are unequal in 'A' and 'B'.
    • At one stage after combining segments of 'A' and 'B' we can definitely get to the point where the sum of these segments are same in 'A' and 'B' as the total sum of both the arrays are same. 

       

 Algorithm:-
 

  • If the sum of 'A' and 'B' are not equal:
    • Return -1.
  • Initializing 'ans', 'i', 'j' with 0.
  • while(i < n && j < m):
    • ans++.
    • 'dif' = 'A[i]' - 'B[j]'.
    • i++.
    • j++.
    • while(dif != 0):
      • if(dif < 0):
        • dif+=A[i].
        • i++.
      • else:
        • dif-=B[j];
        • j++.
  • Return 'ans' which is the required answer.

 

Time Complexity

O(N + M), where 'N' and 'M' are the lengths of the array 'A' and 'B'.

 

We are traversing linearly in 'A' and 'B' and the complexity associated with this is O(N + M). Hence, the overall time complexity is of the order O(N + M).

Space Complexity

O(1).

We are using constant extra space, So the Space Complexity is O(1).

Code Solution
(100% EXP penalty)
Equal Arrays
Full screen
Console