Ugly Number III: Binary Search and Inclusion-Exclusion

Ugly Number III is LeetCode 1201. Given four positive integers n, a, b, and c, find the nth positive integer that is divisible by a, b, or c. This is a medium-difficulty problem, but the technique behind it is genuinely elegant: binary search on the answer combined with the inclusion-exclusion principle.

If you have seen Nth Magical Number, you will recognize the shape of this problem. Ugly Number III extends the same idea from two divisors to three, which makes the counting formula a bit more involved but does not change the overall approach.

Why this problem matters

Ugly Number III sits at the intersection of two important algorithmic ideas. First, binary search on the answer space, where you do not search through an array but instead search through a range of candidate values. Second, a number-theoretic counting formula based on inclusion-exclusion. Problems like this train you to combine mathematical reasoning with algorithmic templates, a skill that shows up in many contest and interview settings.

The key insight

You cannot generate all ugly numbers one by one and stop at the nth one. With n up to 2 * 10^9, that would be far too slow. Instead, you flip the question: "Given a number x, how many positive integers up to x are divisible by a, b, or c?" If you can answer that question efficiently, you can binary search for the smallest x where the count equals n.

The count function uses inclusion-exclusion. The number of integers from 1 to x divisible by a is x // a. But if you just add x // a + x // b + x // c, you double-count numbers divisible by two of them and triple-count numbers divisible by all three. Inclusion-exclusion corrects for that:

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

Each term runs in O(1), so the entire count is O(1). The binary search then runs in O(log(max_val)) iterations, each doing O(1) work.

The solution

from math import gcd

def nthUglyNumber(n, a, b, c):
    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)

    lo, hi = 1, 2 * 10**9

    while lo < hi:
        mid = lo + (hi - lo) // 2
        count = mid // a + mid // b + mid // c - mid // ab - mid // ac - mid // bc + mid // abc

        if count >= n:
            hi = mid
        else:
            lo = mid + 1

    return lo

Let's break this down piece by piece.

LCM precomputation. Before the binary search starts, you precompute lcm(a, b), lcm(a, c), lcm(b, c), and lcm(a, b, c). The LCM of two numbers is x * y // gcd(x, y). For three numbers, lcm(a, b, c) = lcm(lcm(a, b), c). These values are computed once and reused in every iteration.

Search range. lo starts at 1 (the smallest possible answer) and hi starts at 2 * 10^9 (a safe upper bound since n is at most 2 * 10^9 and the smallest divisor is at least 1). You could tighten hi to n * min(a, b, c), but 2 * 10^9 is fine and avoids edge case mistakes.

The count formula. At each midpoint, you compute how many integers from 1 to mid are divisible by a, b, or c. This is the inclusion-exclusion formula. If the count is at least n, the answer might be mid or something smaller, so you set hi = mid. If the count is less than n, you need a larger value, so you set lo = mid + 1.

Convergence. When lo == hi, that is your answer.

Visual walkthrough

Let's trace the binary search for n=5, a=2, b=3, c=5. The LCMs are: lcm(2,3) = 6, lcm(2,5) = 10, lcm(3,5) = 15, lcm(2,3,5) = 30.

Five steps to converge from the range [1, 10] down to the single answer 6. The 5th positive integer divisible by 2, 3, or 5 is indeed 6 (the sequence is 2, 3, 4, 5, 6). With the actual constraints where hi can be up to 2 * 10^9, the binary search still takes at most about 31 iterations, each doing constant work. That is why this approach is so fast.

Complexity analysis

Time: O(log(max_val)). The binary search runs over a range up to 2 * 10^9, so at most about 31 iterations. Each iteration computes the count in O(1). The GCD and LCM precomputations are also O(log(max(a, b, c))) but that is dominated by the binary search.

Space: O(1). You store a handful of variables for the LCMs and the binary search bounds. No extra data structures needed.

The building blocks

1. Binary search on the answer space

The core template is the same one you see in Koko Eating Bananas and Capacity to Ship Packages:

lo, hi = 1, 2 * 10**9

while lo < hi:
    mid = lo + (hi - lo) // 2
    if is_feasible(mid):
        hi = mid
    else:
        lo = mid + 1

return lo

You define a range of candidate answers, check a condition at the midpoint, and narrow down. The condition here is count(mid) >= n instead of a pile-eating feasibility check, but the binary search skeleton is identical.

2. Inclusion-exclusion counting

The counting function is the math that makes this problem unique:

def count(x, a, b, c, ab, ac, bc, abc):
    return x // a + x // b + x // c - x // ab - x // ac - x // bc + x // abc

This counts how many integers in [1, x] are divisible by at least one of a, b, or c. Without inclusion-exclusion, you would overcount numbers like 6 (divisible by both 2 and 3) or 30 (divisible by all three). The alternating add-subtract pattern ensures each number is counted exactly once.

Edge cases

• Two or all three divisors are equal: if a == b, then lcm(a, b) = a, and the formula naturally reduces. No special handling needed.
• One divisor divides another: if a divides b, then every multiple of b is also a multiple of a. The LCM is b, and inclusion-exclusion handles it correctly.
• n = 1: the answer is min(a, b, c), the smallest of the three divisors. The binary search finds this naturally.
• Very large n: the upper bound 2 * 10^9 is safe for the constraints. You could also use n * min(a, b, c) as the upper bound for a tighter range.
• Integer overflow: in Python, integers have arbitrary precision, so this is not a concern. In languages like Java or C++, you need to use long for the LCM computations.

From understanding to recall

The structure of this problem is clean: binary search the answer space, count with inclusion-exclusion, narrow down. You probably follow the logic right now.

But reconstructing it under time pressure is another matter. Was the count formula + + + - - - + or + + - + - +? Do you precompute lcm(a, b, c) as lcm(lcm(a, b), c) or something else? Is the upper bound n * min(a, b, c) or 2 * 10^9? These details are easy to mix up if you have not practiced them recently.

Spaced repetition locks in the pattern. You write the solution from scratch today, again tomorrow, then in a few days. After a few rounds, the inclusion-exclusion formula and the binary search template are automatic. You do not rederive them. You just write them.

LeetCode 1201 is a great SRS candidate because the code is compact (about 15 lines), the math is reusable in related problems, and the formula has just enough terms to trip you up if you have not drilled it.

Related posts

• Binary Search (LeetCode) - The foundational binary search implementation that underpins the search-on-answer pattern
• Koko Eating Bananas - The classic binary search on the answer problem, same template with a different feasibility check
• Nth Magical Number - The two-divisor version of this exact problem, using the same inclusion-exclusion and binary search approach

CodeBricks helps you internalize patterns like binary search with inclusion-exclusion through spaced repetition. Instead of re-solving problems from scratch each time, you build lasting recall of the templates and formulas that matter most in interviews.