Check if 2 arrays of unequal lengths will coincide at any index if you keep repe...
source link: http://codeforces.com/blog/entry/109783
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Check if 2 arrays of unequal lengths will coincide at any index if you keep repeating them.
By mlabeeb, 22 hours ago,
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?
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK