Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

878. Nth Magical Number

Time: $O(\log(\min(A, B) \cdot N))$

Space: $O(1)$

			


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;
  }
};




			


class Solution {
  public int nthMagicalNumber(long n, long a, long b) {
    final int kMod = 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 % kMod);
  }

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




			


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

    while l < r:
      m = (l + r) // 2
      if m // a + m // b - m // lcm >= n:
        r = m
      else:
        l = m + 1

    return l % (10**9 + 7)