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

All Problems

All Solutions