Equal Arrays

4.4

7 votes
Greedy Algorithms, Basics of Greedy Algorithms, Algorithms
Problem

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.

  • Replace any subarray of the array with the sum of the elements in the subarray.

You want to make A and B equal. Find 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 print 1.

Input format

  • The first line contains an integer T, which denotes the number of test cases.
  • The first line of each test case contains two integers N and M, denoting the length of the array A and B.
  • The second line of each test case contains N space-separated integers, elements of array A.
  • The third line of each test case contains M space-separated integers, elements of array B.

Output format

For each test case, print 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 print 1 in a new line.

Constraints

1T101N,M1051A[i],B[i]105

 

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For test case 1: It can be proven that we cannot make A and B equal. Hence, the answer is 1.

For test case 2: 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.

Editor Image

?