Find LCM of two numbers

Problem

Given two integers a and b, compute their least common multiple lcm(a, b) — the smallest positive integer divisible by both inputs.

Inputs: two integers a and b (can be assumed non-negative for the standard definition; handle 0 as a special case).

Examples

Example 1

Input: a = 15, b = 20
Output: 60

Example 2

Input: a = 5, b = 7
Output: 35

Notes

• By convention lcm(0, b) = 0 and lcm(a, 0) = 0.

Solution

Method 1 — Brute force multiples

Intuition

Start from the larger of a and b and check successive multiples until one is divisible by both — simple but can be very slow when numbers are large.

Approach

1. If a == 0 or b == 0 return 0.
2. Let ans = max(a, b).
3. While ans % a != 0 || ans % b != 0: set ans += max(a, b).
4. Return ans.

Code

C++

class Solution {
 public:
  long long lcm(int a, int b) {
    if (a == 0 || b == 0) return 0;
    long long aa = std::llabs((long long)a);
    long long bb = std::llabs((long long)b);
    long long step = aa > bb ? aa : bb;
    long long ans = step;
    while (ans % aa != 0 || ans % bb != 0) ans += step;
    return ans;
  }
};

Go

package main

type Solution struct{}

func (s Solution) lcm(a, b int) int {
  if a == 0 || b == 0 { return 0 }
  aa := abs(a); if abs(b) > aa { aa = abs(b) }
  ans := aa
  for ans%a != 0 || ans%b != 0 { ans += aa }
  return ans
}

func abs(x int) int { if x < 0 { return -x }; return x }

Java

class Solution {
  public int lcm(int a, int b) {
    if (a == 0 || b == 0) return 0;
    int step = Math.abs(a) > Math.abs(b) ? Math.abs(a) : Math.abs(b);
    int ans = step;
    while (ans % a != 0 || ans % b != 0) ans += step;
    return ans;
  }
}

Kotlin

class Solution {
  fun lcm(a: Int, b: Int): Int {
    if (a == 0 || b == 0) return 0
    var step = kotlin.math.abs(a)
    if (kotlin.math.abs(b) > step) step = kotlin.math.abs(b)
    var ans = step
    while (ans % a != 0 || ans % b != 0) ans += step
    return ans
  }
}

Python

class Solution:
  def lcm(self, a: int, b: int) -> int:
    if a == 0 or b == 0: return 0
    step = max(abs(a), abs(b))
    ans = step
    while ans % a != 0 or ans % b != 0:
      ans += step
    return ans

Rust

pub struct Solution;
impl Solution {
  pub fn lcm(&self, a: i64, b: i64) -> i64 {
    if a == 0 || b == 0 { return 0 }
    let mut step = a.abs(); if b.abs() > step { step = b.abs() }
    let mut ans = step;
    while ans % a != 0 || ans % b != 0 { ans += step; }
    ans
  }
}

Complexity

• ⏰ Time complexity: O(lcm(a,b)/max(a,b)) in the worst case — can be very large.
• 🧺 Space complexity: O(1).

Method 2 — Prime factorization

Intuition

Factor both numbers into primes and take the union of primes with the maximum exponent seen for each prime. Multiplying those primes to their chosen exponents yields the LCM.

Approach

1. Factor a and b into prime powers (maps from prime -> exponent).
2. For each prime present in either factorization, take exp = max(exp_a, exp_b).
3. Multiply together prime^exp for all primes to get lcm.

Edge cases: if either a or b is 0, return 0.

Code

C++

#include <map>
#include <cmath>
#include <cstdlib>

class Solution {
 public:
  long long lcm(int a, int b) {
    if (a == 0 || b == 0) return 0;
    auto A = factor(std::llabs((long long)a));
    auto B = factor(std::llabs((long long)b));
    long long res = 1;
    for (auto &kv : A) {
      long long p = kv.first;
      int e = kv.second;
      int eb = B.count(p) ? B[p] : 0;
      for (int i = 0; i < std::max(e, eb); ++i) res *= p;
    }
    for (auto &kv : B) if (!A.count(kv.first)) for (int i = 0; i < kv.second; ++i) res *= kv.first;
    return res;
  }

 private:
  std::map<long long,int> factor(long long n) {
    std::map<long long,int> mp;
    for (long long p = 2; p * p <= n; ++p) {
      while (n % p == 0) { mp[p]++; n /= p; }
    }
    if (n > 1) mp[n]++;
    return mp;
  }
};

Go

package main

type Solution struct{}

func (s Solution) lcm(a, b int) int {
  if a == 0 || b == 0 { return 0 }
  A := s.factor(abs(a))
  B := s.factor(abs(b))
  res := 1
  for p, ea := range A {
    eb := B[p]
    for i := 0; i < max(ea, eb); i++ { res *= p }
  }
  for p, eb := range B { if A[p] == 0 { for i := 0; i < eb; i++ { res *= p } } }
  return res
}

func (s Solution) factor(n int) map[int]int {
  m := map[int]int{}
  p := 2
  for p*p <= n {
    for n%p == 0 {
      m[p]++
      n /= p
    }
    p++
  }
  if n > 1 { m[n]++ }
  return m
}

func abs(x int) int { if x < 0 { return -x }; return x }
func max(a,b int) int { if a>b { return a }; return b }

Java

import java.util.*;
class Solution {
  public int lcm(int a, int b) {
    if (a == 0 || b == 0) return 0;
    Map<Integer,Integer> A = factor(Math.abs(a));
    Map<Integer,Integer> B = factor(Math.abs(b));
    long res = 1;
    for (Map.Entry<Integer,Integer> e : A.entrySet()) {
      int p = e.getKey(); int ea = e.getValue(); int eb = B.getOrDefault(p,0);
      for (int i = 0; i < Math.max(ea, eb); ++i) res *= p;
    }
    for (Map.Entry<Integer,Integer> e : B.entrySet()) if (!A.containsKey(e.getKey())) for (int i = 0; i < e.getValue(); ++i) res *= e.getKey();
    return (int)res;
  }

  private Map<Integer,Integer> factor(int n) {
    Map<Integer,Integer> mp = new HashMap<>();
    for (int p = 2; (long)p * p <= n; ++p) {
      while (n % p == 0) { mp.put(p, mp.getOrDefault(p,0)+1); n /= p; }
    }
    if (n > 1) mp.put(n, mp.getOrDefault(n,0)+1);
    return mp;
  }
}

Kotlin

class Solution {
  fun lcm(a: Int, b: Int): Int {
    if (a == 0 || b == 0) return 0
    val A = factor(kotlin.math.abs(a))
    val B = factor(kotlin.math.abs(b))
    var res = 1
    for ((p, ea) in A) {
      val eb = B.getOrDefault(p, 0)
      repeat(maxOf(ea, eb)) { res *= p }
    }
    for ((p, eb) in B) if (!A.containsKey(p)) repeat(eb) { res *= p }
    return res
  }

  private fun factor(nOrig: Int): MutableMap<Int, Int> {
    var n = nOrig
    val mp = mutableMapOf<Int, Int>()
    var p = 2
    while (p * p <= n) {
      while (n % p == 0) { mp[p] = mp.getOrDefault(p,0) + 1; n /= p }
      p++
    }
    if (n > 1) mp[n] = mp.getOrDefault(n,0) + 1
    return mp
  }
}

Python

class Solution:
  def lcm(self, a: int, b: int) -> int:
    if a == 0 or b == 0:
      return 0
    A = self._factor(abs(a))
    B = self._factor(abs(b))
    res = 1
    for p, ea in A.items():
      eb = B.get(p, 0)
      for _ in range(max(ea, eb)):
        res *= p
    for p, eb in B.items():
      if p not in A:
        for _ in range(eb): res *= p
    return res

  def _factor(self, n: int) -> dict:
    m = {}
    p = 2
    while p * p <= n:
      while n % p == 0:
        m[p] = m.get(p, 0) + 1
        n //= p
      p += 1
    if n > 1:
      m[n] = m.get(n, 0) + 1
    return m

Rust

use std::collections::HashMap;
pub struct Solution;
impl Solution {
  pub fn lcm(&self, a: i64, b: i64) -> i64 {
    if a == 0 || b == 0 { return 0 }
    let A = self.factor(a.abs());
    let B = self.factor(b.abs());
    let mut res = 1i64;
    for (p, ea) in A.iter() {
      let eb = *B.get(p).unwrap_or(&0);
      for _ in 0..std::cmp::max(*ea, eb) { res *= *p; }
    }
    for (p, eb) in B.iter() { if !A.contains_key(p) { for _ in 0..*eb { res *= *p } } }
    res
  }

  fn factor(&self, mut n: i64) -> HashMap<i64,i32> {
    let mut mp = HashMap::new();
    let mut p = 2;
    while p * p <= n {
      while n % p == 0 { *mp.entry(p).or_insert(0) += 1; n /= p; }
      p += 1;
    }
    if n > 1 { *mp.entry(n).or_insert(0) += 1; }
    mp
  }
}

Complexity

Complexity

• ⏰ Time complexity: O(sqrt(max(a,b))) for factoring (worst-case) — expensive for large inputs.
• 🧺 Space complexity: O(k) where k is number of distinct prime factors.

Method 3 — Using GCD

Intuition

Use the identity a * b = lcm(a, b) * gcd(a, b). Rearranged: lcm(a, b) = |a / gcd(a, b) * b|. Dividing first avoids intermediate overflow.

Approach

1. If a == 0 or b == 0, return 0.
2. Compute g = gcd(|a|, |b|) using the Euclidean algorithm.
3. Return abs(a / g * b) (do the division a / g before multiplying by b to reduce overflow risk).

Code

C++

class Solution {
 public:
  long long lcm(int a, int b) {
    if (a == 0 || b == 0) return 0;
    long long g = gcd(a, b);
    return std::llabs((a / g) * (long long)b);
  }

 private:
  long long gcd(long long a, long long b) {
    while (b) { long long t = a % b; a = b; b = t; }
    return a >= 0 ? a : -a;
  }
};

Go

package main

type Solution struct{}

func (s Solution) lcm(a, b int) int {
  if a == 0 || b == 0 { return 0 }
  g := s.gcd(a, b)
  return abs((a/g) * b)
}

func (s Solution) gcd(a, b int) int { for b != 0 { a, b = b, a % b }; if a<0 { return -a }; return a }

Java

class Solution {
  public int lcm(int a, int b) {
    if (a == 0 || b == 0) return 0;
    int g = gcd(a, b);
    return Math.abs((a / g) * b);
  }

  private int gcd(int a, int b) {
    while (b != 0) { int t = a % b; a = b; b = t; }
    return Math.abs(a);
  }
}

Kotlin

class Solution {
  fun lcm(a: Int, b: Int): Int {
    if (a == 0 || b == 0) return 0
    val g = gcd(a, b)
    return kotlin.math.abs((a / g) * b)
  }

  private fun gcd(aOrig: Int, bOrig: Int): Int {
    var a = aOrig
    var b = bOrig
    while (b != 0) {
      val t = a % b; a = b; b = t
    }
    return kotlin.math.abs(a)
  }
}

Python

class Solution:
  def lcm(self, a: int, b: int) -> int:
    if a == 0 or b == 0:
      return 0
    g = self._gcd(a, b)
    return abs((a // g) * b)

  def _gcd(self, a: int, b: int) -> int:
    a, b = abs(a), abs(b)
    while b:
      a, b = b, a % b
    return a

Rust

pub struct Solution;
impl Solution {
  pub fn lcm(&self, a: i64, b: i64) -> i64 {
    if a == 0 || b == 0 { return 0 }
    let g = self.gcd(a, b);
    (a / g * b).abs()
  }

  fn gcd(&self, mut a: i64, mut b: i64) -> i64 {
    a = a.abs(); b = b.abs();
    while b != 0 { let t = a % b; a = b; b = t; }
    a.abs()
  }
}

Complexity

• ⏰ Time complexity: O(log(min(a,b))) due to the Euclidean algorithm.
• 🧺 Space complexity: O(1).