Skip to main content
  1. Problem Solving Solutions/

Smallest Multiple - HackerRank - Project Euler #5

·3 mins read
Project-Euler
Mayukh Datta
Author
Mayukh Datta
Table of Contents

Read the problem statement here:

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

HackerRank:  https://www.hackerrank.com/contests/projecteuler/challenges/euler005/problem

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).

Java code:

import java.util.*; class Solution{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int t = in.nextInt(); while(t– > 0){ int n = in.nextInt(); System.out.println(findLCM(n)); } in.close(); } static long findLCM(int n){ long result = 1; for(int i=2; i<=n; i++){ result = (result * i) / findGCD(result, i); } return result; } static long findGCD(long a, long b){ //Finding GCD using Euclid’s Algorithm if(b == 0){ return a; } return findGCD(b, a % b); } }

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

References: