##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/878.html

# 878. Nth Magical Number

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. 1 <= N <= 10^9
2. 2 <= A <= 40000
3. 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)
}