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

Solution: Math + Binary Search

• Time complexity: O(log(Min(a,b)*n))
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number} n
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
const nthMagicalNumber = function (n, a, b) {
  const gcd = (a, b) => (b ? gcd(b, a % b) : a);

  const MODULO = 10 ** 9 + 7;
  const lcm = (a * b) / gcd(a, b);
  let left = Math.min(a, b);
  let right = n * left;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    const nth = Math.floor(mid / a) + Math.floor(mid / b) - Math.floor(mid / lcm);

    nth >= n ? (right = mid) : (left = mid + 1);
  }
  return left % MODULO;
};