Skip to content

878. Nth Magical Number 👍

  • Time: $O(\log(\min(A, B) \cdot n))$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int nthMagicalNumber(long n, long a, long b) {
    constexpr int kMod = 1'000'000'007;
    const long lcm = a * b / __gcd(a, b);
    long l = min(a, b);
    long r = min(a, b) * n;

    while (l < r) {
      const long m = (l + r) / 2;
      if (m / a + m / b - m / lcm >= n)
        r = m;
      else
        l = m + 1;
    }

    return l % kMod;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public int nthMagicalNumber(long n, long a, long b) {
    final int MOD = 1_000_000_007;
    final long lcm = a * b / gcd(a, b);
    long l = Math.min(a, b);
    long r = Math.min(a, b) * n;

    while (l < r) {
      final long m = (l + r) / 2;
      if (m / a + m / b - m / lcm >= n)
        r = m;
      else
        l = m + 1;
    }

    return (int) (l % MOD);
  }

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

1
2
3
4
5
6
7
8
class Solution:
  def nthMagicalNumber(self, n: int, a: int, b: int) -> int:
    lcm = a * b // math.gcd(a, b)
    l = min(a, b)
    r = min(a, b) * n
    ans = bisect.bisect_left(range(l, r), n,
                             key=lambda m: m // a + m // b - m // lcm) + l
    return ans % (10**9 + 7)