1201. Ugly Number III

1201. Ugly Number III (Medium)

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 <= 109
• 1 <= a * b * c <= 1018
• It is guaranteed that the result will be in range [1, 2 * 109].

Companies:
American Express

Related Topics:
Math, Binary Search, Number Theory

Similar Questions:

• Ugly Number II (Medium)

Solution 1. Binary Answer + Inclusion-exclusion Principle

// OJ: https://leetcode.com/problems/ugly-number-iii/
// Author: github.com/lzl124631x
// Time: O(logN)
// Space: O(1)
class Solution {
    long lcm(long a, long b) { // least common multiple
        return a * b / gcd(a, b);
    }
public:
    int nthUglyNumber(int n, int a, int b, int c) {
        long L = 1, R = 2e9;
        auto le = [&](long M) {
            return M / a + M / b + M / c - M / lcm(a, b) - M / lcm(b, c) - M / lcm(a, c) + M / lcm(lcm(a, b), c);
        };
        while (L <= R) {
            long M = (L + R) / 2, cnt = le(M);
            if (cnt < n) L = M + 1;
            else R = M - 1;
        }
        return L;
    }
};