#1201

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Ugly Number III

Find the nth positive integer divisible by a, b, or c using binary search over the answer space efficiently and accurately.

math binary search combinatorics number theory

Problem Statement

You are given four positive integers n, a, b, and c. An ugly number is any positive integer divisible by a, b, or c. Your task is to return the nth ugly number in increasing order. For example, if n = 3, a = 2, b = 3, and c = 5, the ugly numbers in order are 2, 3, 4, 5..., making the 3rd ugly number 4.

Constraints ensure all inputs are within the range 1 <= n, a, b, c <= 10^9, and the product a * b * c <= 10^18. The output will always be in the range [1, 2 * 10^9]. Your solution should handle large values efficiently and avoid brute-force enumeration, using binary search and mathematical counting techniques instead.

Examples

Example 1

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

Output: 4

The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.

Example 2

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

Output: 6

The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4th is 6.

Example 3

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

Output: 10

The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.

Constraints

1 <= n, a, b, c <= 109
1 <= a * b * c <= 1018
It is guaranteed that the result will be in range [1, 2 * 109].

Solution Approach

Define a counting function

Write a function f(k) that returns the number of ugly numbers less than or equal to k. Use the inclusion-exclusion principle to count numbers divisible by a, b, c, their pairwise LCMs, and the LCM of all three. This counting function is monotonic and forms the basis for binary search.

Binary search over candidate values

Use binary search between 1 and 2 * 10^9 to find the smallest integer k such that f(k) >= n. At each midpoint, compute f(mid) and adjust the search bounds accordingly. This ensures logarithmic convergence to the exact nth ugly number without generating the full sequence.

Return the nth ugly number

Once binary search completes, the lower bound will be the exact nth ugly number. This approach avoids iterating through all previous ugly numbers and handles very large inputs efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(log(maxVal)) per counting evaluation, where maxVal is up to 2 * 10^9, and each count uses O(1) arithmetic operations with LCMs. Space complexity is O(1) as no large arrays are stored.

What Interviewers Usually Probe

Expect candidates to quickly define a counting function using inclusion-exclusion.
Check if they correctly apply binary search over the answer space instead of sequence enumeration.
Watch for handling large integers and potential overflows when computing LCMs.

Common Pitfalls or Variants

Common pitfalls

Forgetting to subtract overcounted numbers when applying inclusion-exclusion.
Using brute-force iteration, which will time out for large n or large a, b, c values.
Failing to handle integer overflow in LCM calculations, especially when a b c is near 10^18.

Follow-up variants

Find nth ugly number for more than three divisors, requiring generalized inclusion-exclusion.
Compute the sum of the first n ugly numbers instead of just the nth.
Adapt the pattern to count numbers divisible by given primes in a dynamic range.

FAQ

What is the fastest approach for Ugly Number III?

Using a counting function with binary search over the answer space is the fastest and most scalable method.

How do I avoid overcounting when applying inclusion-exclusion?

Subtract numbers counted in pairwise LCMs and add back the triple LCM to adjust the total count accurately.

Can I solve this by generating all ugly numbers sequentially?

Sequential generation is too slow for large n; binary search over the answer space is required for efficiency.

How does binary search work for this problem?

You search between 1 and the upper limit, using the counting function f(k) to check if the current midpoint meets or exceeds n ugly numbers.

What issues should I watch for with large inputs?

Ensure LCM calculations do not overflow and use 64-bit integers to handle values up to 10^18 safely.

terminal

Solution

Solution 1: Binary Search + Inclusion-Exclusion Principle

We can transform the problem into: find the smallest positive integer $x$ such that the number of ugly numbers less than or equal to $x$ is exactly $n$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        ab = lcm(a, b)
        bc = lcm(b, c)
        ac = lcm(a, c)
        abc = lcm(a, b, c)
        l, r = 1, 2 * 10**9
        while l < r:
            mid = (l + r) >> 1
            if (
                mid // a
                + mid // b
                + mid // c
                - mid // ab
                - mid // bc
                - mid // ac
                + mid // abc
                >= n
            ):
                r = mid
            else:
                l = mid + 1
        return l

Continue Practicing

#1735 count ways to make array with product #3116 kth smallest amount with single denomination combination #1237 find positive integer solution for a given equation