Welcome to Subscribe On Youtube

878. Nth Magical Number

Description

A positive integer is magical if it is divisible by either a or b.

Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: n = 1, a = 2, b = 3
Output: 2

Example 2:

Input: n = 4, a = 2, b = 3
Output: 6

 

Constraints:

• 1 <= n <= 109
• 2 <= a, b <= 4 * 104

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      private static final int MOD = (int) 1e9 + 7;
  
      public int nthMagicalNumber(int n, int a, int b) {
          int c = a * b / gcd(a, b);
          long l = 0, r = (long) (a + b) * n;
          while (l < r) {
              long mid = l + r >>> 1;
              if (mid / a + mid / b - mid / c >= n) {
                  r = mid;
              } else {
                  l = mid + 1;
              }
          }
          return (int) (l % MOD);
      }
  
      private int gcd(int a, int b) {
          return b == 0 ? a : gcd(b, a % b);
      }
  }
  

• using ll = long long;
  
  class Solution {
  public:
      const int mod = 1e9 + 7;
  
      int nthMagicalNumber(int n, int a, int b) {
          int c = lcm(a, b);
          ll l = 0, r = 1ll * (a + b) * n;
          while (l < r) {
              ll mid = l + r >> 1;
              if (mid / a + mid / b - mid / c >= n)
                  r = mid;
              else
                  l = mid + 1;
          }
          return l % 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