1307. Ugly Number III

• Difficulty: Medium

• Topics: Math, Binary Search

• Similar Questions:

  • Ugly Number II

Problem:

Write a program to find the n-th ugly number.

Ugly numbers are positive integers which are divisible by a or b or c.

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's guaranteed that the result will be in range [1, 2 * 10^9]

Solutions:

class Solution {
public:
    int nthUglyNumber(int n, int A, int B, int C) {
        int left = 1;
        int right = INT_MAX;

        long a = A;
        long b = B;
        long c = C;

        long d = gcm(a, b);

        long e = gcm(a, c);
        e = min(e, long(INT_MAX) );
        long f = gcm(b, c);
        f = min(f, long(INT_MAX) );

        long g = gcm(e, f);

        g = min(g, long(INT_MAX) );

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (countUglyNumber(mid, a, b, c, d, e, f, g) >= n) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
private:
    int countUglyNumber(long num, long a, long b, long c, long d, long e, long f, long g) {
        return  num / a + num / b + num / c - num / d - num / e - num / f + num / g;
    }

    int gcd(int x, int y) {
        if (y > x) {
            return gcd(y, x);
        }

        if (y == 0) return x;
        return gcd(y, x % y);
    }

    long gcm(long x, long y) {
        return (x * y) / gcd(x, y);
    }

};