878 Nth Magical Number
878. Nth Magical Number
1. Question
A positive integer ismagical if it is divisible by eitherA orB.
Return the N-th magical number. Since the answer may be very large, return it modulo10^9 + 7.
Example 1:
Input: N = 1, A = 2, B = 3
Output: 2
Example 2:
Input: N = 4, A = 2, B = 3
Output: 6
Example 3:
Input: N = 5, A = 2, B = 4
Output: 10
Example 4:
Input: N = 3, A = 6, B = 4
Output: 8
Note:
1 <= N <= 10^9
2 <= A <= 40000
2 <= B <= 40000
2. Implementation
(1) Binary Search
思路:
要找出第N个数能被A或B除,我们可以用二分查找在[Math.min(A, B), Long.MAX_VALUE]的范围内找到。在二分查找的过程中,我们先判断如果target number是mid, 它有多少个magic number。如果magic number的数量小于N, 说明mid太小,则将范围缩小到[mid + 1, end], 否则mid太大,范围变为[start, mid]。找magic number的个数,我们可以通过公式 x / A + x / B - x / (A * B /gcd)得到,其中A * B /gcd是A, B是最小公倍数, 减去x / (A * B /gcd)是为了避免计算重复的数字
class Solution {
public int nthMagicalNumber(int N, int A, int B) {
long start = Math.min(A, B);
long end = Long.MAX_VALUE;
long mod = (long)1e9 + 7;
int gcd = getGCD(A, B);
while (start + 1 < end) {
long mid = start + (end - start) / 2;
if (!isValid(A, B, N, gcd, mid)) {
start = mid + 1;
}
else {
end = mid;
}
}
return isValid(A, B, N, gcd, start) ? (int)(start % mod) : (int)(end % mod);
}
public int getGCD(int a, int b) {
while (b > 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
public boolean isValid(int a, int b, int n, int gcd, long target) {
return target / a + target / b - target / ((a * b) / gcd) >= n;
}
}
3. Time & Space Complexity
Binary Search: 时间复杂度O(log(Max)), max表示的是Log.MAX_VALUE, 空间复杂度O(1)
Last updated
Was this helpful?