• + 8 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.

    k1  - - - k2
    x=0       x=4
    v=3       v=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).

    4 6 8 10 12  <- K2
    0 3 6  9 12  <- K1
    4 3 2  1  0  <- Difference
     1 1  1  1   <- 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.

    10 12 14 16 18  <- K2
     3  7 11 15 19  <- K1
     7  5  3  1 -1  <- Difference
      2  2  2  2    <- Rate
    

    The rate isn't a factor of the original distance, therefore they will never meet: 7 % 2 = 1