Ugly Number III — Binary Search and Inclusion-Exclusion Interview

Problem Statement#

An ugly number (in this problem) is positive and divisible by a, b, or c. Return the nth such ugly number.

Constraints:

• 1 <= n, a, b, c <= 10^9
• 1 <= a * b * c <= 10^18
• Answer fits in a 32-bit signed integer.

Input:  n = 3, a = 2, b = 3, c = 5
Output: 4

Input:  n = 5, a = 2, b = 11, c = 13
Output: 10

Why This Problem Matters#

LeetCode 1201 looks like an Ugly Number variant but is actually a binary search plus inclusion-exclusion problem in disguise. It is a Google, Amazon, and Microsoft favorite because it tests whether you can recognize when the heap-DP approach blows up and pivot to a counting argument.

While priority queue interview problems often default to heaps, this question rewards candidates who can see past the pattern and reach for an O(log) solution. It is included here as a foil to teach you when not to use a heap.

The Core Insight#

Count multiples of a, b, or c in [1, x] using inclusion-exclusion: f(x) = x/a + x/b + x/c - x/lcm(a,b) - x/lcm(a,c) - x/lcm(b,c) + x/lcm(a,b,c). Binary search on x to find the smallest x where f(x) >= n.

Visual Dry Run#

n=3, a=2, b=3, c=5

Solution (Optimal)#

from math import gcd
 
class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        def lcm(x, y):
            return x * y // gcd(x, y)
        ab = lcm(a, b)
        ac = lcm(a, c)
        bc = lcm(b, c)
        abc = lcm(ab, c)
 
        def count(x: int) -> int:
            return x // a + x // b + x // c - x // ab - x // ac - x // bc + x // abc
 
        lo, hi = 1, 2 * 10**9
        while lo < hi:
            mid = (lo + hi) // 2
            if count(mid) < n:
                lo = mid + 1
            else:
                hi = mid
        return lo

var nthUglyNumber = function(n, a, b, c) {
    const gcd = (x, y) => y === 0n ? x : gcd(y, x % y);
    const lcm = (x, y) => x / gcd(x, y) * y;
    const A = BigInt(a), B = BigInt(b), C = BigInt(c);
    const AB = lcm(A, B), AC = lcm(A, C), BC = lcm(B, C), ABC = lcm(AB, C);
    const count = (x) => x / A + x / B + x / C - x / AB - x / AC - x / BC + x / ABC;
    let lo = 1n, hi = 2_000_000_000n;
    const N = BigInt(n);
    while (lo < hi) {
        const mid = (lo + hi) / 2n;
        if (count(mid) < N) lo = mid + 1n;
        else hi = mid;
    }
    return Number(lo);
};

Time: O(log(2 * 10^9)) ≈ 31 iterations of constant-time counting. Space: O(1).

Common Mistakes#

• Trying a heap or DP — n can be up to 10^9; you cannot enumerate.
• Computing a * b directly without checking overflow; use Python big ints or BigInt in JS.
• Forgetting the - pairwise + triple inclusion-exclusion structure.
• Setting hi too low; 2 * 10^9 is safe for the constraints.
• Wrong invariant: must search for smallest x with count(x) >= n, not > n.

Interview Tips#

• Verbalize the pattern recognition: "n is up to 10^9 so I cannot enumerate."
• Walk through inclusion-exclusion on a Venn diagram (3 circles).
• Mention that lcm overflows for very large inputs — discuss BigInt or Python.
• Explain why the answer space is monotonic in x (count is non-decreasing).

Follow-up Questions#

• Generalize to k divisors. Hint: 2^k subsets in inclusion-exclusion.
• What if divisors are not pairwise coprime? Hint: lcm handles it correctly.
• Can you do it without binary search? Hint: only with much harder math.
• Find the nth number divisible by exactly one of a, b, c. Hint: subtract pair-overlap counts twice.
• Stream answers for many ns. Hint: precompute and binary-search per query.

Key Takeaways#

• LeetCode 1201 Ugly Number III is binary search plus inclusion-exclusion, not a heap problem.
• Time: O(log(answer_space)). Space: O(1).
• The counting function is the key: f(x) = sum of floors minus pairwise lcms plus triple lcm.
• Always check overflow when multiplying constraint-bound integers.
• Recognizing when to abandon the heap pattern is itself a priority queue interview skill.
• This problem teaches inclusion-exclusion which appears in many counting problems.
• Asked at Google, Amazon, and Microsoft to filter candidates who only memorize patterns.