# 1201. Ugly Number III

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

Example 4:

``````Input: n = 1000000000, a = 2, b = 217983653, c = 336916467
Output: 1999999984
``````

Constraints:

• `1 <= n, a, b, c <= 10^9`
• `1 <= a * b * c <= 10^18`
• It is guaranteed that the result will be in range `[1, 2 * 10^9]`.

``````class Solution {
public:
int nthUglyNumber(int n, int a, int b, int c) {
int left = 0, right = 2e9;
while (left < right) {
int mid = left + (right - left) / 2;
int cnt = mid / a + mid / b + mid / c - mid / lcm(a, b) - mid / lcm(b, c) - mid / lcm(a, c) + mid / lcm(a, lcm(b, c));
if (cnt < n) {
left = mid + 1;
} else {
right = mid;
}
}
return right;
}
long gcd(long a, long b) {
return a == 0 ? b : gcd(b % a, a);
}
long lcm(long a, long b) {
return a * b / gcd(a, b);
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1201

Ugly Number II

Ugly Number

Super Ugly Number

Max Points on a Line

https://leetcode.com/problems/ugly-number-iii/

https://leetcode.com/problems/ugly-number-iii/discuss/387539/cpp-Binary-Search-with-picture-and-Binary-Search-Template

https://leetcode.com/problems/ugly-number-iii/discuss/387780/JavaC%2B%2B-Binary-Search-with-Venn-Diagram-Explain-Math-Formula

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation