HackerRank - Project Euler #5 - Smallest Multiple

Read the problem statement here:



We need to find the Least Common Multiple (LCM) of all the numbers from 1 to N so as to find the smallest positive number that can be evenly divided by all the N numbers.

We first have to calculate Greatest Common Divisor (GCD) or Highest Common Factor (HCF) to calculate the LCM of all the numbers.

What is GCD?

If we find all the prime factors of each of the numbers then multiplying the common factors gives us the GCD.
12 = 2 * 2 * 3
24 = 2 * 2 * 2 * 3
48 = 2 * 2 * 2 * 2 *3
GCD = Multiplication of common prime factors
GCD(12, 24, 48) = 2 * 2 * 3 = 12
There is another way of expressing it:
Listing all the factors
12 = 1, 2, 3, 4, 6, 12
24 = 1, 2, 3, 4, 6, 8, 12, 24
48 = 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
GCD = Pick the greatest common factor
GCD(12, 24, 48) = 12

What is LCM?

It is the smallest positive number that is the multiple of two or more numbers.
Multiples of 30 = 30, 60, 90, 120, ...
Multiples of 45 = 45, 90, 135, 180, ...
Multiples of 15 = 15, 30, 45, 60, 75, 90, 105, ...
LCM = Least Common Multiple
LCM(30, 45, 15) = 90

How to compute LCM?

\[LCM(a, b) = \dfrac{a * b}{GCD(a, b)}\]
The above relation only holds true for two numbers.
\[LCM(a, b, c) \neq \dfrac{a * b * c}{GCD(a, b, c)}\]
To solve this problem we need to find the LCM of N numbers. Therefore, to find the LCM of more than two numbers we need an array consisting of the numbers. But, in this case, we can do that by initializing result = 1 and then start traversing from i=2 to i=n. For each iteration we calculate, result = LCM(result, i) = (result * i) / gcd(result, i).

My Solution in Java:


The time complexity of this code is \(O(n)\).

It passed all the test cases on HackerRank.

References:




Comments