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

All Problems

All Solutions