Nth Magical Number

Nth Magical Number

What is this problem about?

The Nth Magical Number problem asks you to find the n-th smallest positive integer that is divisible by either a or b. This Nth Magical Number coding problem uses binary search on the answer combined with the inclusion-exclusion principle via LCM.

Why is this asked in interviews?

Meta, Amazon, Google, and Bloomberg ask this hard problem because it requires combining binary search on the answer with the mathematical formula for counting numbers divisible by a or b up to a given value. The math and binary search interview pattern is the core, and the LCM calculation is key.

Algorithmic pattern used

Binary search on the answer. For a given number x, the count of magical numbers ≤ x = floor(x/a) + floor(x/b) - floor(x/lcm(a,b)) (inclusion-exclusion). Binary search for the smallest x where this count ≥ n. Answer must be taken mod 10^9+7.

Example explanation

a=2, b=3, n=4. LCM(2,3)=6.

• x=6: count = 6/2 + 6/3 - 6/6 = 3+2-1 = 4 ≥ n=4. Feasible.
• x=5: count = 5/2 + 5/3 - 5/6 = 2+1-0 = 3 < 4. Not feasible. Minimum x where count ≥ 4 = 6. The 4th magical number is 6. (2,3,4,6 → 4th is 6 ✓).

Common mistakes candidates make

• Forgetting inclusion-exclusion (double-counting multiples of lcm(a,b)).
• Binary search bounds too small (upper bound should be n * min(a,b)).
• Not computing LCM correctly: lcm(a,b) = a/gcd(a,b)*b (divide first to avoid overflow).
• Forgetting the modulo for the final answer.

Interview preparation tip

Nth-element problems with a counting formula are natural binary search on answer problems. The key: define f(x) = count of valid elements ≤ x. If f is monotonically non-decreasing, binary search finds the smallest x where f(x) ≥ n. Here, the inclusion-exclusion formula for f(x) is the crucial mathematical component. Practice LCM/GCD computations and inclusion-exclusion counting — they appear together in many number theory binary search problems at Google and Bloomberg.