Skip to content

1201. Ugly Number III

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  int nthUglyNumber(int n, long a, long b, long c) {
    const long ab = a * b / __gcd(a, b);
    const long ac = a * c / __gcd(a, c);
    const long bc = b * c / __gcd(b, c);
    const long abc = a * bc / __gcd(a, bc);
    int l = 1;
    int r = 2'000'000'000;

    while (l < r) {
      const int m = l + (r - l) / 2;
      if (m / a + m / b + m / c - m / ab - m / ac - m / bc + m / abc >= n)
        r = m;
      else
        l = m + 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
class Solution {
  public int nthUglyNumber(int n, long a, long b, long c) {
    final long ab = a * b / gcd(a, b);
    final long ac = a * c / gcd(a, c);
    final long bc = b * c / gcd(b, c);
    final long abc = a * bc / gcd(a, bc);
    int l = 1;
    int r = 2_000_000_000;

    while (l < r) {
      final int m = (l + r) / 2;
      if (m / a + m / b + m / c - m / ab - m / ac - m / bc + m / abc >= n)
        r = m;
      else
        l = m + 1;
    }

    return l;
  }

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

1
2
3
4
5
6
7
8
9
class Solution:
  def nthUglyNumber(self, n: int, a: int, b: int, c: int) -> int:
    ab = a * b // math.gcd(a, b)
    ac = a * c // math.gcd(a, c)
    bc = b * c // math.gcd(b, c)
    abc = a * bc // math.gcd(a, bc)
    return bisect.bisect_left(
        range(2 * 10**9), n,
        key=lambda m: m // a + m // b + m // c - m // ab - m // ac - m // bc + m // abc)