I was practicing for an upcoming interview on HackerRank yesterday night. One of these problems was difficult for me to solve and was phrased something like this:

You have n bunnies, each of which starts at position 0. Each bunny has its own jump amount. What is the next closest point where all bunnies can be in the same position again?

For example:

• Three bunnies with jump amounts 2, 3, and 4 will next meet at 12.
• Two bunnies with jump amounts 10 and 15 will next meet at 30.

I understood that part of this problem had to do with factors, but every time I tried to look up the mathematical name of the concept I needed to familiarize myself with, I always found Greatest Common Divisor (or GCD) instead which was incorrect.

While talking to a friend about this, they pointed out that the concept I was looking for is called the Least Common Multiple (or LCM). They also pointed out that many languages have support for the GCD and LCM in the standard library. Sure enough, it exists in Haskell:

-- | @'lcm' x y@ is the smallest positive integer that both @x@ and @y@ divide.
lcm :: Integral a => a -> a -> a
lcm _ 0         =  0
lcm 0 _         =  0
lcm x y         =  abs ((x `quot` (gcd x y)) * y)

So, the solution in Haskell is:

main :: IO ()
main = do
  jumps <- readNumbers <$> getLine
  print $ foldl lcm 1 jumps
 
readNumbers :: String -> [Integer]
readNumbers = fmap read . words