I don't know if this is a classic problem or not but I can't seem to find a solution for it.
Consider two arrays a = [1, 2, 3, 4, 5] and b = [3, 6, 6]. You are also given two indexes a_ind = 0 and b_ind = 0. In one move you can add 1 to both a_ind and b_ind, if the index for any array goes out of bound then reset that index to 0. The task is to calculate the number of moves it would take such that the value a[a_ind] == b[b_ind] or state that it is impossible.
The brute force method would be to append both arrays to themselves x times. Where x = lcm(lenght(a), lenght(b)) / length(a) for the array a and x = lcm(lenght(a), lenght(b)) / length(b) for the array b, the above arrays would become:
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
3 6 6 3 6 6 3 6 6 3 6 6 3 6 6
The condition is satisfied at the 12th move. However this method would give TLE on any platform.
What would be an optimal approach for solving it?
This is from the top of my head but it can be solved in O(NM). In above example assuming answer is at xth position, if its due to first 3 in array A and B coinciding: x=5i+3, x=3j+1. 5i+3=3j+1, 5i-3j=-2, solve with linear diophantine equations. Find minimum x for all equal pairs = O(NM).
What if the length of a = 10^5 and b = 10^5-1. In such case a linear or logarithmic solution is required.
That's why I said it's from the top of my head.
This is easy. You'll visit all positions $$$\mod gcd(len(a),len(b))$$$. Now, if theres duplicate in those modulo sets, you have the answer YES else NO. The second part is what I am thinking how to do fast.
After that, if you find the visited states starting from $$$i = 0 \mod{gcd(n,m)}$$$, then, you can use the same visited array to calculate for array b. Since for all the same modulos, they'll visit the same states, except the starting position / number of moves will be different. Simple prefix array /suffix array to find the nearest will work.
I'd love to chat for more clarifications.
You can use Bézout's identity + (hash)map to get a $$$O((N + M) \log (N + M))$$$ :
$$$a[i]$$$ and $$$b[j]$$$ will coincide iff there are $$$x, y$$$ such that $$$i + nx = j + my \iff nx - my = j - i \iff j - i$$$ is a multiple of $$$\gcd(n, m)$$$ so you just need to keep track of values at the indexes mod $$$\gcd(n, m)$$$ with a map/hashmap.