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) == 0
On the default example
0 3 4 2
I began by picturing K2 was ahead but not moving.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 of4
(clearly it will jump over it):Imagine the alternative case where
K2
is also moving:v2 = 2
If
v1 > v2
we knowv1
will eventually catch up. If on each jump K1 advances 3 steps and K2 advances 2 steps, then K1 is gaining on K2 by3 - 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
).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.The rate isn't a factor of the original distance, therefore they will never meet:
7 % 2 = 1