Is Ugly Number III easy or hard?

Ugly Number III is considered a medium difficulty problem. The binary search itself is straightforward, but combining it with the inclusion-exclusion counting formula and LCM calculations requires solid understanding of math and number theory.

How to solve Ugly Number III in O(log n)?

Use binary search on the answer. For any candidate number x, compute how many integers ≤ x are divisible by a, b, or c using the inclusion-exclusion formula with LCM values. Adjust the binary search boundaries until the smallest x with count ≥ n is found.

What is the best approach for Ugly Number III?

The most efficient solution uses binary search combined with the inclusion-exclusion principle. Instead of generating numbers, it searches for the smallest value x where at least n numbers less than or equal to x are divisible by a, b, or c. Each step computes counts using LCM values, giving a time complexity of O(log R) with constant space.

Is Ugly Number III asked at Google/Amazon/Meta?

Variants of this problem appear in interviews at companies like Amazon, Google, and other large tech firms because it tests binary search on the answer and number theory concepts such as GCD and LCM. Similar counting problems are common in system and algorithm interviews.

What data structure is used in Ugly Number III?

The optimal solution mainly relies on arithmetic operations and binary search rather than complex data structures. A priority queue (min-heap) can be used in a simulation approach, but it is less efficient for large constraints.

What is the time complexity of Ugly Number III?

The optimal algorithm runs in O(log R) time where R is the search range (up to about 2 × 10^9). Each binary search step performs constant-time arithmetic operations such as division and LCM calculations. Space complexity is O(1).

Ugly Number III Python or Java solution approach?

Both Python and Java implementations typically follow the same strategy: compute GCD and LCM values, perform binary search on the range, and apply the inclusion-exclusion formula to count valid numbers. The logic remains identical across languages.

Description Hints 2 Solution Video 5:49

1201. Ugly Number III

Medium31.9% acceptance3 companies

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 n^th 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 3^rd 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 4^th 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 5^th is 10.

Constraints:

1 <= n, a, b, c <= 10⁹
1 <= a * b * c <= 10¹⁸
It is guaranteed that the result will be in range [1, 2 * 10⁹].

Asked at 3 companies

American Express Amazon Meta

Topics

Hints open one at a time

Hint 1

Write a function f(k) to determine how many ugly numbers smaller than k. As f(k) is non-decreasing, try binary search.

Hint 2

Find all ugly numbers in [1, LCM(a, b, c)] (LCM is Least Common Multiple). Use inclusion-exclusion principle to expand the result.

5:49

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution