big_aL's blog

Check if 2 arrays of unequal lengths will coincide at any index if you keep repeating them.
By big_aL, 2 years ago, In English

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?

  • Vote: I like it
  • +32
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like 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).

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What if the length of a = 10^5 and b = 10^5-1. In such case a linear or logarithmic solution is required.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      That's why I said it's from the top of my head.

      → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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.

→ Reply
  • »
    »
    2 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply