Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/878.html
878. Nth Magical Number
Level
Hard
Description
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^9
2 <= A <= 40000
2 <= B <= 40000
Solution
The N-th magical number before the modulo operation can always be held by a long
data type, considering the ranges of N
, A
and B
.
To simplify the scenario, if A
is greater than B
, then swap A
and B
so that the case is always A <= B
.
If B
is divisible by A
(for example, A = 2
and B = 10
), then any number that is divisible by B
is also divisible by A
, so the N-th magical number is A * N
.
For other cases, calculate the least common multiple of A
and B
, which is lcm
. The number of magical numbers from 1 to lcm
is count = lcm / A + lcm / B - 1
. Define a “group” to be a group of numbers from the previous common divisor exclusive to the next common divisor inclusive. Calculate groups = N / count
and remainder = N % count
. The greatest number in the last complete group is num = lcm * groups
. If remainder
is 0, the N-th magical number is num
. Otherwise, find the remainder
-th magical number in the first group, which is magicalNum
, and add magicalNum
to num
. After the steps, num
is the N-th magical number.
-
class Solution { public int nthMagicalNumber(int N, int A, int B) { final int MODULO = 1000000007; if (A > B) { int temp = A; A = B; B = temp; } if (B % A == 0) { long num = (long) A * (long) N; return (int) (num % MODULO); } else { int lcm = lcm(A, B); int count = lcm / A + lcm / B - 1; int groups = N / count; long num = (long) lcm * (long) groups; int remainder = N % count; if (remainder == 0) return (int) (num % MODULO); else { int magicalNum = 1; int num1 = A, num2 = B; for (int i = 1; i <= remainder; i++) { if (num1 < num2) { magicalNum = num1; num1 += A; } else { magicalNum = num2; num2 += B; } } num %= MODULO; num += magicalNum; return (int) (num % MODULO); } } } public int lcm(int num1, int num2) { return num1 * num2 / gcd(num1, num2); } public int gcd(int num1, int num2) { num1 = Math.abs(num1); num2 = Math.abs(num2); if (num1 == 0 && num2 == 0) return 1; while (num1 != 0 && num2 != 0) { if (num1 > num2) { int temp = num1; num1 = num2; num2 = temp; } num2 %= num1; } return num1 == 0 ? num2 : num1; } }
-
// OJ: https://leetcode.com/problems/nth-magical-number/ // Time: O(A + B) // Space: O(1) class Solution { public: int nthMagicalNumber(int n, int a, int b) { long mod = 1e9 + 7, L = a * b / gcd(a, b), M = L / a + L / b - 1, q = n / M, r = n % M, ans = (long)q * L % mod; int val[2] = {0, 0}; for (int i = 0; i < r; ++i) { auto [x, y] = val; if (x <= y) val[0] += a; if (y <= x) val[1] += b; } ans += min(val[0], val[1]); return ans % 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) }