How to solve this Problem in O(N) or O(N * logN) or anything better than O(N^2).

Revision en2, by shekabhi1208, 2021-12-10 20:32:07

Hello codeforces, I want to know whether there is any solution to this problem that is better than the naive O(N ^ 2) or not?

Problem:

You are given two arrays A and B. In each step, you can set A[i] = A[i] — B[i] if A[i] >= B[i]. Determine the minimum number of steps that are required to make all values of array A equal.

Print the minimum number of steps that are required to make all values of array A equal. If it is not possible, then print -1.

Constraints:

1 <= N, A[i], B[i] <= 5000

Sample Input

2

5 6

4 3

Sample Output

-1

Sample Input:

5

5 7 10 5 15

2 2 1 3 5

Sample Output:

8

Link to the Problem

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English shekabhi1208 2021-12-10 20:32:07 521 Tiny change: 'le Input\n2\n5 6\n' -> 'le Input\n\n2\n5 6\n'
en1 English shekabhi1208 2021-12-10 20:22:13 375 Initial revision (published)