Formatted question description: https://leetcode.ca/all/1201.html

1201. Ugly Number III

Level

Medium

Description

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]

Solution

Use binary search. Initially set low to be 1 and high to be 2 * 10^9. The condition of binary search is low < high. Each time set mid to be the average of low and high, and calculate the number of ugly numbers that are less than or equal to mid, which can be calculated using inclusion-exclusion principle. If the number of ugly numbers is less than n, then obviously the n-th ugly number is greater than mid, so set low = mid + 1. Otherwise, the n-th ugly number may be mid or less than mid, so set high = mid. After the search ends, return low.

class Solution {
    public int nthUglyNumber(int n, int a, int b, int c) {
        long lcmAB = a / gcd(a, b) * b;
        long lcmBC = b / gcd(b, c) * c;
        long lcmAC = a / gcd(a, c) * c;
        long lcmABC = lcmAB / gcd(lcmAB, c) * c;
        long low = 1, high = 2000000000;
        while (low < high) {
            long mid = (high - low) / 2 + low;
            long count = mid / a + mid / b + mid / c - mid / lcmAB - mid / lcmBC - mid / lcmAC + mid / lcmABC;
            if (count < n)
                low = mid + 1;
            else
                high = mid;
        }
        return (int) low;
    }

    public long gcd(long a, long b) {
        if (a == 0 && b == 0)
            return 1;
        while (a != 0 && b != 0) {
            if (a > b) {
                long temp = a;
                a = b;
                b = temp;
            }
            b %= a;
        }
        return a == 0 ? b : a;
    }
}

All Problems

All Solutions