An ugly number is a positive integer that is divisible by a, b, or c.
Given four integers n, a, b, and c, return the nth ugly number.
Example 1:
Input: n = 3, a = 2, b = 3, c = 5 Output: 4 Explanation: 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 Explanation: 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 Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.
Constraints:
1 <= n, a, b, c <= 1091 <= a * b * c <= 1018[1, 2 * 109].In #1201 Ugly Number III, the task is to find the nth positive integer that is divisible by at least one of three numbers a, b, or c. Instead of generating numbers sequentially, the efficient strategy uses Binary Search combined with the Inclusion–Exclusion Principle.
The idea is to search for the smallest number x such that the count of integers ≤ x divisible by a, b, or c is at least n. To compute this count efficiently, use LCM to handle overlaps: numbers divisible by multiple values must be adjusted using inclusion–exclusion. During binary search, calculate the count of valid numbers and move the search boundaries accordingly.
This approach avoids brute force enumeration and works efficiently even for large constraints. The key insight is converting the problem into a counting function evaluated within a binary search range.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search with Inclusion-Exclusion | O(log(R)) where R is the search range | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Write a function f(k) to determine how many ugly numbers smaller than k. As f(k) is non-decreasing, try binary search.
Find all ugly numbers in [1, LCM(a, b, c)] (LCM is Least Common Multiple). Use inclusion-exclusion principle to expand the result.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like Ugly Number III are commonly used in technical interviews at large tech companies. They test a candidate's ability to combine binary search with mathematical reasoning such as LCM and inclusion–exclusion.
Binary search is used because the count of numbers divisible by a, b, or c increases monotonically as the range increases. This property allows us to efficiently search for the smallest value where the count reaches n without checking every number.
The optimal approach uses binary search combined with the inclusion–exclusion principle. For any number x, you count how many integers up to x are divisible by a, b, or c using LCM calculations. Binary search then finds the smallest x that produces at least n valid numbers.
The inclusion–exclusion principle is essential for correctly counting numbers divisible by multiple values without double counting. Least Common Multiple (LCM) is used to compute overlaps between pairs and triples of divisibility conditions.