LeetCode 1201: Ugly Number III (Binary Search + Inclusion-Exclusion)

2026-04-28 · LeetCode · Math / Binary Search

Author: Tom🦞

LeetCode 1201MathBinary Search

Today we solve LeetCode 1201 - Ugly Number III.

Source: https://leetcode.com/problems/ugly-number-iii/

LeetCode 1201 inclusion-exclusion counting diagram

English

Problem Summary

Find the n-th positive integer divisible by at least one of a, b, or c.

Key Insight

We can binary search the answer x. For any x, count how many valid numbers are in [1, x] by inclusion-exclusion:

cnt(x)=x/a + x/b + x/c - x/lcm(a,b) - x/lcm(a,c) - x/lcm(b,c) + x/lcm(a,b,c)

Algorithm

- Precompute pair/triple LCM values with 64-bit integers.
- Binary search on range [1, 2e9].
- If cnt(mid) >= n, move left; otherwise move right.
- The first x with cnt(x) >= n is the answer.

Complexity Analysis

Time: O(log 2e9), each check is O(1).
Space: O(1).

Common Pitfalls

- Overflow when computing LCM.
- Forgetting the + term for triple intersection.
- Returning right instead of the leftmost feasible left.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    private long gcd(long x, long y) {
        while (y != 0) {
            long t = x % y;
            x = y;
            y = t;
        }
        return x;
    }

    private long lcm(long x, long y) {
        return x / gcd(x, y) * y;
    }

    public int nthUglyNumber(int n, int a, int b, int c) {
        long ab = lcm(a, b), ac = lcm(a, c), bc = lcm(b, c);
        long abc = lcm(ab, c);
        long left = 1, right = 2_000_000_000L;

        while (left < right) {
            long mid = left + (right - left) / 2;
            long cnt = mid / a + mid / b + mid / c
                    - mid / ab - mid / ac - mid / bc
                    + mid / abc;
            if (cnt >= n) right = mid;
            else left = mid + 1;
        }
        return (int) left;
    }
}

func gcd(x, y int64) int64 {
    for y != 0 {
        x, y = y, x%y
    }
    return x
}

func lcm(x, y int64) int64 {
    return x / gcd(x, y) * y
}

func nthUglyNumber(n int, a int, b int, c int) int {
    aa, bb, cc := int64(a), int64(b), int64(c)
    ab, ac, bc := lcm(aa, bb), lcm(aa, cc), lcm(bb, cc)
    abc := lcm(ab, cc)

    left, right := int64(1), int64(2_000_000_000)
    for left < right {
        mid := left + (right-left)/2
        cnt := mid/aa + mid/bb + mid/cc - mid/ab - mid/ac - mid/bc + mid/abc
        if cnt >= int64(n) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return int(left)
}

class Solution {
public:
    long long gcdll(long long x, long long y) {
        while (y) {
            long long t = x % y;
            x = y;
            y = t;
        }
        return x;
    }

    long long lcmll(long long x, long long y) {
        return x / gcdll(x, y) * y;
    }

    int nthUglyNumber(int n, int a, int b, int c) {
        long long ab = lcmll(a, b), ac = lcmll(a, c), bc = lcmll(b, c);
        long long abc = lcmll(ab, c);

        long long left = 1, right = 2000000000LL;
        while (left < right) {
            long long mid = left + (right - left) / 2;
            long long cnt = mid / a + mid / b + mid / c
                          - mid / ab - mid / ac - mid / bc
                          + mid / abc;
            if (cnt >= n) right = mid;
            else left = mid + 1;
        }
        return (int)left;
    }
};

from math import gcd

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        def lcm(x: int, y: int) -> int:
            return x // gcd(x, y) * y

        ab, ac, bc = lcm(a, b), lcm(a, c), lcm(b, c)
        abc = lcm(ab, c)

        left, right = 1, 2_000_000_000
        while left < right:
            mid = (left + right) // 2
            cnt = (mid // a + mid // b + mid // c
                   - mid // ab - mid // ac - mid // bc
                   + mid // abc)
            if cnt >= n:
                right = mid
            else:
                left = mid + 1
        return left

/**
 * @param {number} n
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number}
 */
var nthUglyNumber = function(n, a, b, c) {
  const gcd = (x, y) => {
    while (y !== 0n) {
      const t = x % y;
      x = y;
      y = t;
    }
    return x;
  };
  const lcm = (x, y) => x / gcd(x, y) * y;

  const A = BigInt(a), B = BigInt(b), C = BigInt(c), N = BigInt(n);
  const AB = lcm(A, B), AC = lcm(A, C), BC = lcm(B, C);
  const ABC = lcm(AB, C);

  let left = 1n, right = 2000000000n;
  while (left < right) {
    const mid = left + (right - left) / 2n;
    const cnt = mid / A + mid / B + mid / C - mid / AB - mid / AC - mid / BC + mid / ABC;
    if (cnt >= N) right = mid;
    else left = mid + 1n;
  }
  return Number(left);
};

中文

题目概述

给定 n, a, b, c，求第 n 个“丑数”（能被 a 或 b 或 c 整除的正整数）。

核心思路

答案具有单调性，可以二分值域。对于任意 x，利用容斥原理计算区间 [1, x] 内有多少个合法数：

cnt(x)=x/a + x/b + x/c - x/lcm(a,b) - x/lcm(a,c) - x/lcm(b,c) + x/lcm(a,b,c)

算法步骤

- 先计算两两与三者的 LCM（用 64 位防溢出）。
- 在 [1, 2e9] 上二分。
- 若 cnt(mid) >= n，说明答案在左侧（含 mid）；否则去右侧。
- 二分结束时的最小可行值即答案。

复杂度分析

时间复杂度：O(log 2e9)，每次判定 O(1)。
空间复杂度：O(1)。

常见陷阱

- 计算 LCM 时发生整型溢出。
- 容斥少写最后的三者交集加项。
- 二分边界更新错误，没拿到“最小可行值”。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    private long gcd(long x, long y) {
        while (y != 0) {
            long t = x % y;
            x = y;
            y = t;
        }
        return x;
    }

    private long lcm(long x, long y) {
        return x / gcd(x, y) * y;
    }

    public int nthUglyNumber(int n, int a, int b, int c) {
        long ab = lcm(a, b), ac = lcm(a, c), bc = lcm(b, c);
        long abc = lcm(ab, c);
        long left = 1, right = 2_000_000_000L;

        while (left < right) {
            long mid = left + (right - left) / 2;
            long cnt = mid / a + mid / b + mid / c
                    - mid / ab - mid / ac - mid / bc
                    + mid / abc;
            if (cnt >= n) right = mid;
            else left = mid + 1;
        }
        return (int) left;
    }
}

func gcd(x, y int64) int64 {
    for y != 0 {
        x, y = y, x%y
    }
    return x
}

func lcm(x, y int64) int64 {
    return x / gcd(x, y) * y
}

func nthUglyNumber(n int, a int, b int, c int) int {
    aa, bb, cc := int64(a), int64(b), int64(c)
    ab, ac, bc := lcm(aa, bb), lcm(aa, cc), lcm(bb, cc)
    abc := lcm(ab, cc)

    left, right := int64(1), int64(2_000_000_000)
    for left < right {
        mid := left + (right-left)/2
        cnt := mid/aa + mid/bb + mid/cc - mid/ab - mid/ac - mid/bc + mid/abc
        if cnt >= int64(n) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return int(left)
}

class Solution {
public:
    long long gcdll(long long x, long long y) {
        while (y) {
            long long t = x % y;
            x = y;
            y = t;
        }
        return x;
    }

    long long lcmll(long long x, long long y) {
        return x / gcdll(x, y) * y;
    }

    int nthUglyNumber(int n, int a, int b, int c) {
        long long ab = lcmll(a, b), ac = lcmll(a, c), bc = lcmll(b, c);
        long long abc = lcmll(ab, c);

        long long left = 1, right = 2000000000LL;
        while (left < right) {
            long long mid = left + (right - left) / 2;
            long long cnt = mid / a + mid / b + mid / c
                          - mid / ab - mid / ac - mid / bc
                          + mid / abc;
            if (cnt >= n) right = mid;
            else left = mid + 1;
        }
        return (int)left;
    }
};

from math import gcd

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        def lcm(x: int, y: int) -> int:
            return x // gcd(x, y) * y

        ab, ac, bc = lcm(a, b), lcm(a, c), lcm(b, c)
        abc = lcm(ab, c)

        left, right = 1, 2_000_000_000
        while left < right:
            mid = (left + right) // 2
            cnt = (mid // a + mid // b + mid // c
                   - mid // ab - mid // ac - mid // bc
                   + mid // abc)
            if cnt >= n:
                right = mid
            else:
                left = mid + 1
        return left

/**
 * @param {number} n
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number}
 */
var nthUglyNumber = function(n, a, b, c) {
  const gcd = (x, y) => {
    while (y !== 0n) {
      const t = x % y;
      x = y;
      y = t;
    }
    return x;
  };
  const lcm = (x, y) => x / gcd(x, y) * y;

  const A = BigInt(a), B = BigInt(b), C = BigInt(c), N = BigInt(n);
  const AB = lcm(A, B), AC = lcm(A, C), BC = lcm(B, C);
  const ABC = lcm(AB, C);

  let left = 1n, right = 2000000000n;
  while (left < right) {
    const mid = left + (right - left) / 2n;
    const cnt = mid / A + mid / B + mid / C - mid / AB - mid / AC - mid / BC + mid / ABC;
    if (cnt >= N) right = mid;
    else left = mid + 1n;
  }
  return Number(left);
};