Ugly number iii

Math Binary Search Combinatorics Number Theory

31.3% acceptance

Feb 25, 2026

1317

518

An ugly number is a positive integer that is divisible by a, b, or c. Given four integers n, a, b, and c, return the nth ugly number.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn nth_ugly_number(n: i32, a: i32, b: i32, c: i32) -> i32 {
    fn gcd(x: i64, y: i64) -> i64 {
      if y == 0 { x } else { gcd(y, x % y) }
    }
    fn lcm(x: i64, y: i64) -> i64 {
      x / gcd(x, y) * y
    }

    let a = a as i64;
    let b = b as i64;
    let c = c as i64;
    let ab = lcm(a, b);
    let bc = lcm(b, c);
    let ac = lcm(a, c);
    let abc = lcm(ab, c);

    let count = |x: i64| -> i64 {
      x / a + x / b + x / c - x / ab - x / bc - x / ac + x / abc
    };

    let mut lo: i64 = 1;
    let mut hi: i64 = 2_000_000_000;
    let n = n as i64;
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      if count(mid) >= n {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    lo as i32
  }
}