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 <= 1092 <= a, b <= 4 * 104
Solutions
Solution 1
PythonJavaC++Go
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(code-box)
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);
}
}(code-box)
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;
}
};(code-box)
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)
}(code-box)
