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.

• Java
• C++
• Python
• Go

• 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