### HackerRank - Project Euler #5 - Smallest Multiple

Read the problem statement here:

Project Euler: https://projecteuler.net/problem=5

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 = 12There 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.

## Comments

## Post a Comment