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;
}
}