We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
On the default example 0 3 4 2 I began by picturing K2 was ahead but not moving.
k1---k2x=0x=4v=3v=0
Now we just have to see if K1 will land on 4 as it hops by.
This is a simple matter of whether v1 is a factor of 4 (clearly it will jump over it):
(x2-x1)%v1=(4-0)%3=1
Imagine the alternative case where K2 is also moving: v2 = 2
If v1 > v2 we know v1 will eventually catch up. If on each jump K1 advances 3 steps and K2 advances 2 steps, then K1 is gaining on K2 by 3 - 2 = 1 each jump (each jump they'll be 1 less apart than the jump before). Now K1 just has to close that original distance (4).
4681012<-K2036912<-K143210<-Difference1111<-Rate
If the rate at which the distance is closing can add up to the original distance between them (4), you know they'll eventually meet.
Now take the example 3 4 10 2 where they do not meet.
Number Line Jumps
You are viewing a single comment's thread. Return to all comments →
Explaining
(x2 - x1) % (v1 - v2) == 0On the default example
0 3 4 2I began by picturing K2 was ahead but not moving.Now we just have to see if K1 will land on
4as it hops by.This is a simple matter of whether
v1is a factor of4(clearly it will jump over it):Imagine the alternative case where
K2is also moving:v2 = 2If
v1 > v2we knowv1will eventually catch up. If on each jump K1 advances 3 steps and K2 advances 2 steps, then K1 is gaining on K2 by3 - 2 = 1each jump (each jump they'll be 1 less apart than the jump before). Now K1 just has to close that original distance (4).If the
rate at which the distance is closingcan add up to the original distance between them (4), you know they'll eventually meet.Now take the example
3 4 10 2where they do not meet.The rate isn't a factor of the original distance, therefore they will never meet:
7 % 2 = 1