Nth Magical Number — Hard Problem & Solution

A positive integer is magical if it is divisible by a or by b. Return the n-th magical number, modulo 10^9 + 7.

Difficulty: Hard
Topics: Math, Binary Search, Number Theory
Asked at: Amazon, Google, Apple
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

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

Compute l = lcm(a, b) = a / gcd(a, b) * b.
Define count(x) = x/a + x/b - x/l.
Binary search the smallest x >= 1 with count(x) >= n, using min(a, b) * n as a safe upper bound.
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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 213 math problems · the whole catalogue