How to Solve Ugly Number III

This problem requires determining the nth ugly number divisible by given integers a, b, or c. The most efficient approach uses a counting function combined with binary search over the valid answer space. By evaluating how many ugly numbers exist below a candidate value, we can quickly converge to the exact nth ugly number without generating all previous numbers explicitly.

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

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 abc 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.

How GhostInterview Helps

• GhostInterview provides a step-by-step walkthrough for defining the counting function f(k) efficiently.
• It simulates the binary search process over the valid answer space, highlighting midpoint evaluation and bound adjustment.
• It flags common mistakes like overcounting in inclusion-exclusion and integer overflow to guide correct implementation.

Topic Pages

• Math
• Binary Search
• Combinatorics
• Number Theory

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.