Nth Magical Number

Hard
715.

Nth Magical Number

Nth Magical Number is a hard coding problem on math, binary search and number theory, asked in Amazon, Google and Apple interviews.

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

Return the n-th magical number, modulo 10^9 + 7.

Example 1

Input
n = 1, a = 2, b = 3
Output
2
Explanation
The magical numbers start 2, 3, 4, 6, 8, 9, …

Example 2

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

Example 3

Input
n = 5, a = 2, b = 4
Output
10
Explanation
Every multiple of 4 is also a multiple of 2, so the sequence is just the even numbers.

Constraints

  • 1 <= n <= 1000000000
  • 2 <= a, b <= 40000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var nthMagicalNumber = function(n, a, b) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Nth Magical Number — Solution in Python, Java & C++

Nth Magical Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Nth Magical Number is a hard coding problem on math, binary search and number theory, asked in Amazon, Google and Apple interviews.

Problem statement

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

Return the n-th magical number, modulo 10^9 + 7.

Example 1

Input: n = 1, a = 2, b = 3
Output: 2
Explanation: The magical numbers start 2, 3, 4, 6, 8, 9, …

Example 2

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

Example 3

Input: n = 5, a = 2, b = 4
Output: 10
Explanation: Every multiple of 4 is also a multiple of 2, so the sequence is just the even numbers.

Constraints

  • 1 <= n <= 1000000000
  • 2 <= a, b <= 40000

Hints for Nth Magical Number

  1. Hint 1

    Counting magical numbers up to x is easy: x/a + x/b - x/lcm(a,b) by inclusion–exclusion.

  2. Hint 2

    That count is non-decreasing in x, so binary search for the smallest x whose count reaches n.

  3. Hint 3

    Apply the modulo only to the final answer — never inside the counting, or the search breaks.

How to solve Nth Magical Number

Binary search on the answer with an inclusion–exclusion counting function. Counting multiples is exact and monotone, so the boundary of 'count reaches n' is the n-th magical number.

Approach

  1. Compute l = lcm(a, b) = a / gcd(a, b) * b.
  2. Define count(x) = x/a + x/b - x/l.
  3. Binary search the smallest x >= 1 with count(x) >= n, using min(a, b) * n as a safe upper bound.
  4. Return x % (10^9 + 7).

Why it works

Inclusion–exclusion is exact because the numbers divisible by both a and b are precisely the multiples of their lcm. The count only rises with x and rises by at least one at each magical number, so the smallest x reaching n is that n-th number itself.

Complexity

  • Time — O(log(min(a,b) · n))
  • Space — O(1)

Pitfalls

  • Reducing modulo inside count destroys monotonicity and the search returns nonsense.
  • a * b can overflow before dividing; compute the lcm as a / gcd * b.
  • The upper bound min(a,b) * n reaches 4 × 10^13, so the search variables need 64 bits.

Reference solution

Python

from math import gcd

def nthMagicalNumber(n: int, a: int, b: int) -> int:
    MOD = 1000000007
    l = a // gcd(a, b) * b
    lo, hi = 1, min(a, b) * n
    while lo < hi:
        mid = (lo + hi) // 2
        if mid // a + mid // b - mid // l >= n:
            hi = mid
        else:
            lo = mid + 1
    return lo % MOD

Java

public static int nthMagicalNumber(int n, int a, int b) {
    final long MOD = 1000000007L;
    long g = gcdMagic(a, b);
    long l = (long) a / g * b;
    long lo = 1, hi = (long) Math.min(a, b) * n;
    while (lo < hi) {
        long mid = (lo + hi) / 2;
        long count = mid / a + mid / b - mid / l;
        if (count >= n) hi = mid;
        else lo = mid + 1;
    }
    return (int) (lo % MOD);
}

static long gcdMagic(long x, long y) {
    while (y != 0) { long t = x % y; x = y; y = t; }
    return x;
}

C++

static long long gcdMagic(long long x, long long y) {
    while (y != 0) { long long t = x % y; x = y; y = t; }
    return x;
}

int nthMagicalNumber(int n, int a, int b) {
    const long long MOD = 1000000007LL;
    long long l = (long long) a / gcdMagic(a, b) * b;
    long long lo = 1, hi = (long long) min(a, b) * n;
    while (lo < hi) {
        long long mid = (lo + hi) / 2;
        long long count = mid / a + mid / b - mid / l;
        if (count >= n) hi = mid;
        else lo = mid + 1;
    }
    return (int) (lo % MOD);
}

JavaScript

var nthMagicalNumber = function(n, a, b) {
    var MOD = 1000000007;
    var gcd = function(x, y) {
        while (y !== 0) {
            var t = x % y;
            x = y;
            y = t;
        }
        return x;
    };
    var l = (a / gcd(a, b)) * b;
    var lo = 1, hi = Math.min(a, b) * n;
    while (lo < hi) {
        var mid = Math.floor((lo + hi) / 2);
        var count = Math.floor(mid / a) + Math.floor(mid / b) - Math.floor(mid / l);
        if (count >= n) hi = mid;
        else lo = mid + 1;
    }
    return lo % MOD;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue

Learn the technique: Binary Search