Find LCM of two numbers - Tutorial [Updated]

Problem Statement: Find lcm of two numbers.

Examples:

Example 1:
Input: num1 = 4,num2 = 8
Output: 8


Example 2:
Input: num1 = 3,num2 = 6
Output: 6

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1:Brute force

Intuition: Simply traverse from 1 to min(a,b) and check for every number.

Approach:

Find gcd using brute force.
Traverse from 1 to min(a,b).
And check if i is divisible by both a and b.If yes store it in the answer.
Find the maximum value of i which divides both a and b.
To find lcm simply divide (a*b) by gcd of a and b.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a = 4, b = 8;
	int gcd;
	for (int i = 1; i <= min(a, b); i++) {
		if (a % i == 0 && b % i == 0) {
			gcd = i;
		}
	}
	int lcm = (a * b) / gcd;
	cout <<"The LCM of the two given numbers is "<<lcm;

}

Output:

The LCM of the two given numbers is 8

Time Complexity: O(N).

Space Complexity: O(1).

Java Code

public class Main {
  public static void main(String args[]) {
    int a = 4, b = 8;
    int gcd = 1;
    for (int i = 1; i <= Math.min(a, b); i++) {
      if (a % i == 0 && b % i == 0) {
        gcd = i;
      }
    }
    int lcm = (a * b) / gcd;
    System.out.print("The LCM of the two given numbers is "+lcm);

  }
}

Output:

The LCM of the two given numbers is 8

Time Complexity: O(N).

Space Complexity: O(1).

Solution 2: Using Euclidean’s theorem.

Intuition: Gcd is the greatest number which is divided by both a and b.If a number is divided by both a and b, it is should be divided by (a-b) and b as well.Using this we can find gcd in log(min(a,b)) and hence lcm.

Approach:

First find gcd using euclidean’s algorithm,

Recursively call gcd(b,a%b) function till the base condition is hit.
b==0 is the base condition.When base condition is hit return a,as gcd(a,0) is equal to a.
Once we get gcd,we can find lcm using formula lcm = (a*b)/gcd.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	return gcd(b, a % b);
}
int main()
{
	int a = 4, b = 8;
	int g = gcd(a, b);
	int lcm = (a * b) / g;
	cout <<"The LCM of the two given numbers is "<<lcm;
}

Output:

The LCM of the two given numbers is 8

Time Complexity: O(log_ɸmin(a,b)),where ɸ is 1.61.

Space Complexity: O(1).

Java Code

public class Main {
  static int gcd(int a, int b) {
    if (b == 0) {
      return a;
    }
    return gcd(b, a % b);
  }
  public static void main(String args[]) {
    int a = 4, b = 8;
    int gcd = gcd(a, b);
    int lcm = (a * b) / gcd;
    System.out.print("The LCM of the two given numbers is "+lcm);
  }
}

Output:

The LCM of the two given numbers is 8

Time Complexity: O(log_ɸmin(a,b)),where ɸ is 1.61.

Space Complexity: O(1).

Special thanks to Pranav Padawe for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article