Problem
A positive integer is magical if it is divisible by either A or B.
Return the N-th magical number. Since the answer may be very large, return it modulo 10^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^92 <= A <= 400002 <= B <= 40000
Solution: Math + Binary Search
Let n denote the number of numbers <= X that are divisible by either A or B.
n = X / A + X / B – X / lcm(A, B) = X / A + X / B – X / (A * B / gcd(A, B))
Binary search for the smallest X such that n >= N
Time complexity: O(log(1e9*4e5)
Space complexity: O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua // Running time: 0 ms class Solution { public: int nthMagicalNumber(int N, int A, int B) { const int kMod = 1000000007; long l = 2; long r = static_cast<long>(1e9 * 4e5); int d = gcd(A, B); while (l < r) { long m = (r - l) / 2 + l; if (m / A + m / B - m / (A * B / d) < N) l = m + 1; else r = m; } return l % kMod; } private: int gcd(int a, int b) { if (a % b == 0) return b; return gcd(b, a % b); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment