Problem

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.

Examples

Example 1

1
2
3
4
5
6
7


    
    
    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

1
2
3
4
5
6
7


    
    
    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

1
2
3
4
5
6
7


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

Solution

Method 1 – Binary Search and Inclusion-Exclusion

Intuition

We can count how many numbers ≤ x are divisible by a, b, or c using inclusion-exclusion. Use binary search to find the smallest x such that the count is at least n.

Approach

  1. Use binary search on the answer in [1, 2e9].
  2. For each mid, count numbers ≤ mid divisible by a, b, or c using:
    • count = mid//a + mid//b + mid//c - mid//lcm(a,b) - mid//lcm(a,c) - mid//lcm(b,c) + mid//lcm(a,b,c)
  3. If count < n, search higher; else, search lower.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int nthUglyNumber(int n, int a, int b, int c) {
        long l = 1, r = 2000000000L;
        long ab = lcm(a, b), ac = lcm(a, c), bc = lcm(b, c), abc = lcm(a, lcm(b, c));
        while (l < r) {
            long m = l + (r - l) / 2;
            long cnt = m/a + m/b + m/c - m/ab - m/ac - m/bc + m/abc;
            if (cnt < n) l = m + 1;
            else r = m;
        }
        return (int)l;
    }
    long lcm(long x, long y) { return x * y / gcd(x, y); }
    long gcd(long x, long y) { return y == 0 ? x : gcd(y, x % y); }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

def nthUglyNumber(n, a, b, c):
    from math import gcd
    def lcm(x, y): return x * y // gcd(x, y)
    ab, ac, bc = lcm(a, b), lcm(a, c), lcm(b, c)
    abc = lcm(a, bc)
    l, r = 1, 2 * 10**9
    while l < r:
        m = (l + r) // 2
        cnt = m//a + m//b + m//c - m//ab - m//ac - m//bc + m//abc
        if cnt < n:
            l = m + 1
        else:
            r = m
    return l

Complexity

  • ⏰ Time complexity: O(log(max) * log(max(a,b,c))) — Binary search and lcm/gcd.
  • 🧺 Space complexity: O(1) — Only a few variables used.