Ugly Number III

Ugly Number III

What is this problem about?

The Ugly Number III interview question takes a different turn. Here, "ugly numbers" are defined as positive integers divisible by a, b, or c. Given n, a, b, and c, you need to find the $n$-th such number. Because the values of n and the divisors can be very large, you cannot use the sequence generation methods used in previous versions.

Why is this asked in interviews?

This is a high-level Math and Number Theory coding problem often seen in advanced rounds at companies like Amazon. it tests your knowledge of the Inclusion-Exclusion Principle and your ability to use Binary Search on a result space. It’s a test of whether you can recognize when a linear search is impossible and apply mathematical logic to jump to the answer.

Algorithmic pattern used

The Math, Number Theory, Binary Search, Combinatorics interview pattern used here involves searching for the answer in the range [1, 2*10^9]. For a given number X, you can calculate how many numbers up to X are divisible by a, b, or c using the formula: $Count(X) = (X/a + X/b + X/c) - (X/lcm(a,b) + X/lcm(b,c) + X/lcm(a,c)) + (X/lcm(a,b,c))$. Since this function is monotonically increasing, Binary Search is the perfect tool to find the smallest X where Count(X) >= n.

Example explanation

If $n=2$, $a=2, b=3, c=5$:

1. We want the 2nd number divisible by 2, 3, or 5.
2. Divisible by 2: 2, 4, 6...
3. Divisible by 3: 3, 6, 9...
4. Divisible by 5: 5, 10... The sequence is 2, 3, 4, 5, 6... The 2nd number is 3. In the algorithm, we would binary search for a value where the Inclusion-Exclusion count equals 2.

Common mistakes candidates make

The most difficult part is implementing the Least Common Multiple (LCM) correctly to avoid integer overflow, especially when multiplying large numbers. Candidates also often forget the "exclusion" and "inclusion" steps, simply adding the counts and resulting in overcounting numbers like 6 (which is divisible by both 2 and 3).

Interview preparation tip

Master the Inclusion-Exclusion Principle for counting problems. Also, get comfortable with Binary Search on Answer, which is a powerful technique when you can easily verify a potential solution but can't easily generate it directly. This pattern is essential for solving "find the n-th element" problems in large ranges.