There are N stones arranged in a circle. A frog sits on the first stone. The frog keeps jumping in clock-wise direction from stone to stone. It skips the stones in increments of 1 for each jump. ie, for the first jump it will skip 0 stones, it skips one stone for the 2nd jump, 2 stones for the 3rd jump and so on. The task is, given the number of stones N, find out if the frog will reach all the stones.
Eg:
N=1 ---> true
N=2 ---> true --> jumps=(1,2)
N=3 ---> false --> jumps=(1,2,1,1,2,1,1,2,1.....)
N=4 ---> true --> jumps=(1,2,4,3)
I have tried out for different values for N. All I could see was, if N is a power of 2 then all stones can be reached. Also if the any stone is visited more than once before visiting all the stones, then the answer is false. I could not find a reasoning for the observations and hence could not prove it.
CodePudding user response：
I think you're thinking about this the wrong way. Don't get me wrong, it's cool to do mathematical analysis and come out with a simple result, like, "All stones can be reached if and only if N is a power of 2." (And in fact, I believe that that result is correct.) But you don't need to find that sort of result in order to write an algorithm that can answer the question.
Instead, your algorithm can just simulate the frog's jumps (which you've obviously already figured out how to do), and see if it hits every stone. The only tricky part is that the frog plans to continue jumping forever, and obviously you want your algorithm to finish in a finite amount of time. The key insight is that the frog's sequence of jumps will always end up in a loop, so you only need to continue simulating the sequence long enough to be sure that you've entered the loop and completed one pass through it.
How do we know this?
To see why, imagine that we know that the frog has just jumped from stone #i to stone #j. Is that enough to tell us where the frog will jump to next? The answer is "yes"; we don't know whether the frog thinks it skipped j−i−1 stones vs. N j−i−1 stones vs. 2N j−i−1 stones or whatnot, but it doesn't matter, because the next stone it lands on doesn't depend on whether the next jump skips j−i stones vs. N j−i stones vs. 2N j−i stones — these are all equivalent. So if we know its last jump then we know its next jump, and if we know its next jump then we know the jump after that, and so on: so this one jump is enough to determine the whole rest of the sequence of stones.
This means that there at most N2 possible "states" that the sequence can be in, always determined by the prior stone and the next stone, where each state fully determines all subsequent states. So if you simulate the sequence through at least N2 states, then either you've visited every state exactly once or you've visited some state at least twice (by the pigeonhole principle), so you've necessarily hit all the states you're going to, which means you've necessarily landed on all the stones that you're going to.
That gives you an algorithm in O(N2) time and O(N) space.
You can potentially improve this by
- tracking which states you've already visited, and terminating as soon as you find that you've returned to a state.
- tracking how many stones you've already landed on, and terminating as soon as you find that you've landed on all of them.
which would complete in O(N) time if you're right that "if the any stone is visited more than once before visiting all the stones, then the answer is false", while still behaving correctly (and still within O(N2) time) if that theory is wrong.