1201. Ugly Number III
Description
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 <= 109
1 <= a * b * c <= 1018
- It is guaranteed that the result will be in range
[1, 2 * 109]
.
Solutions
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$.
For a positive integer $x$, there are $\left\lfloor \frac{x}{a} \right\rfloor$ numbers divisible by $a$, $\left\lfloor \frac{x}{b} \right\rfloor$ numbers divisible by $b$, $\left\lfloor \frac{x}{c} \right\rfloor$ numbers divisible by $c$, $\left\lfloor \frac{x}{lcm(a, b)} \right\rfloor$ numbers divisible by both $a$ and $b$, $\left\lfloor \frac{x}{lcm(a, c)} \right\rfloor$ numbers divisible by both $a$ and $c$, $\left\lfloor \frac{x}{lcm(b, c)} \right\rfloor$ numbers divisible by both $b$ and $c$, and $\left\lfloor \frac{x}{lcm(a, b, c)} \right\rfloor$ numbers divisible by $a$, $b$, and $c$ at the same time. According to the inclusion-exclusion principle, the number of ugly numbers less than or equal to $x$ is:
$$ \left\lfloor \frac{x}{a} \right\rfloor + \left\lfloor \frac{x}{b} \right\rfloor + \left\lfloor \frac{x}{c} \right\rfloor - \left\lfloor \frac{x}{lcm(a, b)} \right\rfloor - \left\lfloor \frac{x}{lcm(a, c)} \right\rfloor - \left\lfloor \frac{x}{lcm(b, c)} \right\rfloor + \left\lfloor \frac{x}{lcm(a, b, c)} \right\rfloor $$
We can use binary search to find the smallest positive integer $x$ such that the number of ugly numbers less than or equal to $x$ is exactly $n$.
Define the left boundary of binary search as $l=1$ and the right boundary as $r=2 \times 10^9$, where $2 \times 10^9$ is the maximum value given by the problem. In each step of binary search, we find the middle number $mid$. If the number of ugly numbers less than or equal to $mid$ is greater than or equal to $n$, it means that the smallest positive integer $x$ falls in the interval $[l,mid]$, otherwise it falls in the interval $[mid+1,r]$. During the binary search process, we need to continuously update the number of ugly numbers less than or equal to $mid$ until we find the smallest positive integer $x$.
The time complexity is $O(\log m)$, where $m = 2 \times 10^9$. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|