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.
- 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 <= 10000000002 <= a, b <= 40000
Hints for Nth Magical Number
Hint 1
Counting magical numbers up to
xis easy:x/a + x/b - x/lcm(a,b)by inclusion–exclusion.Hint 2
That count is non-decreasing in
x, so binary search for the smallestxwhose count reachesn.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
- Compute
l = lcm(a, b) = a / gcd(a, b) * b. - Define
count(x) = x/a + x/b - x/l. - Binary search the smallest
x >= 1withcount(x) >= n, usingmin(a, b) * nas 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
countdestroys monotonicity and the search returns nonsense. a * bcan overflow before dividing; compute the lcm asa / gcd * b.- The upper bound
min(a,b) * nreaches4 × 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 % MODJava
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