Skip to content

1201. Ugly Number III

Description

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.

 

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

Solutions

Solution 1: Binary Search + Inclusion-Exclusion Principle

We can transform the problem into: find the smallest positive integer \(x\) such that the number of ugly numbers less than or equal to \(x\) is exactly \(n\).

For a positive integer \(x\), there are \(\left\lfloor \frac{x}{a} \right\rfloor\) numbers divisible by \(a\), \(\left\lfloor \frac{x}{b} \right\rfloor\) numbers divisible by \(b\), \(\left\lfloor \frac{x}{c} \right\rfloor\) numbers divisible by \(c\), \(\left\lfloor \frac{x}{lcm(a, b)} \right\rfloor\) numbers divisible by both \(a\) and \(b\), \(\left\lfloor \frac{x}{lcm(a, c)} \right\rfloor\) numbers divisible by both \(a\) and \(c\), \(\left\lfloor \frac{x}{lcm(b, c)} \right\rfloor\) numbers divisible by both \(b\) and \(c\), and \(\left\lfloor \frac{x}{lcm(a, b, c)} \right\rfloor\) numbers divisible by \(a\), \(b\), and \(c\) at the same time. According to the inclusion-exclusion principle, the number of ugly numbers less than or equal to \(x\) is:

\[ \left\lfloor \frac{x}{a} \right\rfloor + \left\lfloor \frac{x}{b} \right\rfloor + \left\lfloor \frac{x}{c} \right\rfloor - \left\lfloor \frac{x}{lcm(a, b)} \right\rfloor - \left\lfloor \frac{x}{lcm(a, c)} \right\rfloor - \left\lfloor \frac{x}{lcm(b, c)} \right\rfloor + \left\lfloor \frac{x}{lcm(a, b, c)} \right\rfloor \]

We can use binary search to find the smallest positive integer \(x\) such that the number of ugly numbers less than or equal to \(x\) is exactly \(n\).

Define the left boundary of binary search as \(l=1\) and the right boundary as \(r=2 \times 10^9\), where \(2 \times 10^9\) is the maximum value given by the problem. In each step of binary search, we find the middle number \(mid\). If the number of ugly numbers less than or equal to \(mid\) is greater than or equal to \(n\), it means that the smallest positive integer \(x\) falls in the interval \([l,mid]\), otherwise it falls in the interval \([mid+1,r]\). During the binary search process, we need to continuously update the number of ugly numbers less than or equal to \(mid\) until we find the smallest positive integer \(x\).

The time complexity is \(O(\log m)\), where \(m = 2 \times 10^9\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
        ab = lcm(a, b)
        bc = lcm(b, c)
        ac = lcm(a, c)
        abc = lcm(a, b, c)
        l, r = 1, 2 * 10**9
        while l < r:
            mid = (l + r) >> 1
            if (
                mid // a
                + mid // b
                + mid // c
                - mid // ab
                - mid // bc
                - mid // ac
                + mid // abc
                >= n
            ):
                r = mid
            else:
                l = mid + 1
        return l

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int nthUglyNumber(int n, int a, int b, int c) {
        long ab = lcm(a, b);
        long bc = lcm(b, c);
        long ac = lcm(a, c);
        long abc = lcm(ab, c);
        long l = 1, r = 2000000000;
        while (l < r) {
            long mid = (l + r) >> 1;
            if (mid / a + mid / b + mid / c - mid / ab - mid / bc - mid / ac + mid / abc >= n) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return (int) l;
    }

    private long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    private long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int nthUglyNumber(int n, int a, int b, int c) {
        long long ab = lcm(a, b);
        long long bc = lcm(b, c);
        long long ac = lcm(a, c);
        long long abc = lcm(ab, c);
        long long l = 1, r = 2000000000;
        while (l < r) {
            long long mid = (l + r) >> 1;
            if (mid / a + mid / b + mid / c - mid / ab - mid / bc - mid / ac + mid / abc >= n) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    long long lcm(long long a, long long b) {
        return a * b / gcd(a, b);
    }

    long long gcd(long long a, long long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func nthUglyNumber(n int, a int, b int, c int) int {
    ab, bc, ac := lcm(a, b), lcm(b, c), lcm(a, c)
    abc := lcm(ab, c)
    var l, r int = 1, 2e9
    for l < r {
        mid := (l + r) >> 1
        if mid/a+mid/b+mid/c-mid/ab-mid/bc-mid/ac+mid/abc >= n {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return l
}

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

func lcm(a, b int) int {
    return a * b / gcd(a, b)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function nthUglyNumber(n: number, a: number, b: number, c: number): number {
    const ab = lcm(BigInt(a), BigInt(b));
    const bc = lcm(BigInt(b), BigInt(c));
    const ac = lcm(BigInt(a), BigInt(c));
    const abc = lcm(BigInt(a), bc);
    let l = 1n;
    let r = BigInt(2e9);
    while (l < r) {
        const mid = (l + r) >> 1n;
        const count =
            mid / BigInt(a) +
            mid / BigInt(b) +
            mid / BigInt(c) -
            mid / ab -
            mid / bc -
            mid / ac +
            mid / abc;
        if (count >= BigInt(n)) {
            r = mid;
        } else {
            l = mid + 1n;
        }
    }
    return Number(l);
}

function gcd(a: bigint, b: bigint): bigint {
    return b === 0n ? a : gcd(b, a % b);
}

function lcm(a: bigint, b: bigint): bigint {
    return (a * b) / gcd(a, b);
}

Comments