Make It Equal!

4

3 votes
Greedy algorithm
Problem

You are given two arrays. Your task is to make the two arrays equal by applying following operation.

Operation: Choose a subarray in either of the two arrays and replace the entire subarray with the sum of elements of that subarray. You can perform this operation any number of times.

eg: if you have two arrays [1,2,1,1] and [3,1,1], you can choose a subarray in 1st array [1,2,1,1] from i = 1 to i = 3 and replace the entire subarray [1,2,1] with 4 and it becomes [4,1].

Print the maximum length of the two arrays that can be equal.

Equal array means for every 1 <= i <= k where k is the length of the two arrays a[i] = b[i].

If it is not possible to make arrays equal print -1.

Input Format:

First line contains n, the size of first array A 

Second line contains n integers the elements of array A

Third line contains m, the size of second array B

Fourth line contains m integers the elements of array B 

Constraints:
1 ≤ n ≤ 3⋅10^5
1 ≤ Ai ≤ 10^9
1 ≤ m ≤ 3⋅10^5
1 ≤ Bi ≤ 10^9  

Output Format:

Print the length of the largest array equal to both the arrays. If no such array is present print -1.

Sample Input
3
1000000 1 1
2
1 1
Sample Output
-1
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation

It is not possible to make the arrays equal.

Contributers:
Editor Image

?