Welcome to Subscribe On Youtube

878. Nth Magical Number

Description

A positive integer is magical if it is divisible by either a or b.

Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

 Input: n = 1, a = 2, b = 3 Output: 2

Example 2:

 Input: n = 4, a = 2, b = 3 Output: 6

 

Constraints:

  • 1 <= n <= 109
  • 2 <= a, b <= 4 * 104

Solutions

  • class Solution { private static final int MOD = (int) 1e9 + 7; public int nthMagicalNumber(int n, int a, int b) { int c = a * b / gcd(a, b); long l = 0, r = (long) (a + b) * n; while (l < r) { long mid = l + r >>> 1; if (mid / a + mid / b - mid / c >= n) { r = mid; } else { l = mid + 1; } } return (int) (l % MOD); } private int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } } 
  • using ll = long long; class Solution { public: const int mod = 1e9 + 7; int nthMagicalNumber(int n, int a, int b) { int c = lcm(a, b); ll l = 0, r = 1ll * (a + b) * n; while (l < r) { ll mid = l + r >> 1; if (mid / a + mid / b - mid / c >= n) r = mid; else l = mid + 1; } return l % mod; } }; 
  • class Solution: def nthMagicalNumber(self, n: int, a: int, b: int) -> int: mod = 10**9 + 7 c = lcm(a, b) r = (a + b) * n return bisect_left(range(r), x=n, key=lambda x: x // a + x // b - x // c) % mod 
  • func nthMagicalNumber(n int, a int, b int) int { c := a * b / gcd(a, b) const mod int = 1e9 + 7 r := (a + b) * n return sort.Search(r, func(x int) bool { return x/a+x/b-x/c >= n }) % mod } func gcd(a, b int) int { if b == 0 { return a } return gcd(b, a%b) }

All Problems

All Solutions