Nth Magical Number: Binary Search and Inclusion-Exclusion

A positive integer is magical if it is divisible by either a or b. Given three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 10^9 + 7.

This is LeetCode 878: Nth Magical Number, and it combines binary search on the answer with a classic counting trick from combinatorics. The key insight is that you do not need to enumerate magical numbers one by one. Instead, you can count how many magical numbers exist below any value in O(1) time, and then binary search for the smallest value where that count equals n.

Why this problem matters

Nth Magical Number teaches you the "binary search on the answer" pattern, one of the most versatile techniques in competitive programming and interviews. Instead of building the answer incrementally, you flip the question: "Given a candidate answer x, is it large enough?" If you can answer that question efficiently, you can binary search over the answer space.

This pattern shows up in problems like Koko Eating Bananas, Split Array Largest Sum, and many more. Nth Magical Number adds a twist by requiring the inclusion-exclusion principle to do the counting, which makes it a clean exercise in combining math with binary search.

The approach: binary search on the answer

The magical numbers form an increasing sequence: the union of multiples of a and multiples of b, sorted and deduplicated. We want the nth element of this sequence.

Counting magical numbers up to x. How many positive integers up to x are divisible by a or b? By the inclusion-exclusion principle:

count(x) = x // a + x // b - x // lcm(a, b)

The first term counts multiples of a. The second counts multiples of b. The third subtracts the multiples of both (which are multiples of the LCM), since they were counted twice. The LCM can be computed as a * b // gcd(a, b).

Binary search. We want the smallest x such that count(x) >= n. This is a classic binary search on a monotonic function:

• Set lo = min(a, b) (the first magical number).
• Set hi = n * min(a, b) (an upper bound, since every min(a,b)-th number is magical).
• While lo < hi, compute mid = (lo + hi) // 2. If count(mid) >= n, search left (hi = mid). Otherwise search right (lo = mid + 1).

When the loop ends, lo is the answer.

The solution

from math import gcd

def nthMagicalNumber(n, a, b):
    MOD = 10**9 + 7
    lcm = a * b // gcd(a, b)

    lo, hi = min(a, b), n * min(a, b)
    while lo < hi:
        mid = (lo + hi) // 2
        if mid // a + mid // b - mid // lcm >= n:
            hi = mid
        else:
            lo = mid + 1

    return lo % MOD

Visual walkthrough

Let's trace the binary search for n=4, a=2, b=3. The LCM of 2 and 3 is 6. Our search space starts at lo=2, hi=8.

The binary search narrows the range from [2, 8] down to [6, 6] in just three iterations. Each step computes count(mid) in O(1) using the inclusion-exclusion formula, then decides which half of the range to keep. The answer, 6, is the 4th magical number: the sequence is 2, 3, 4, 6.

Complexity analysis

The binary search runs over a range of size n * min(a, b), so it takes O(log(n * min(a, b))) iterations. Each iteration does O(1) work (integer division and comparison). The GCD computation at the start is O(log(min(a, b))) via Euclid's algorithm, which is dominated by the binary search.

Building blocks

This problem is built on two fundamental patterns:

Binary search on the answer. Instead of constructing the sequence and picking the nth element, you ask "is x large enough to contain at least n magical numbers?" and binary search over x. This reframing works whenever the feasibility check is monotonic (if x works, so does x + 1) and efficient (O(1) or O(n) per check). The same pattern appears in Koko Eating Bananas (binary search on eating speed), Split Array Largest Sum (binary search on the max subarray sum), and Sqrt(x) (binary search on the integer square root).

Inclusion-exclusion counting. Counting elements in the union of two sets by adding the individual counts and subtracting the intersection. Here the intersection is multiples of the LCM. This is a foundational combinatorics technique that appears in problems involving GCD, LCM, and set unions. Once you recognize the pattern, the counting formula writes itself.

Edge cases to watch for

• a equals b: every magical number is a multiple of a, so the answer is simply n * a. The formula handles this correctly because lcm(a, a) = a, so count(x) = x/a + x/a - x/a = x/a.
• One divides the other: if a divides b (or vice versa), then every multiple of b is already a multiple of a. The LCM equals b, and the formula reduces to count(x) = x/a. Again, no special case needed.
• Large n: with n up to 10^9 and a, b up to 40000, the upper bound n * min(a, b) can be around 4 * 10^13. This fits in a 64-bit integer (Python handles big integers natively), but in languages like Java or C++ you need to use long.
• Modular arithmetic: the problem asks for the answer modulo 10^9 + 7. Apply the modulo only at the very end, after the binary search converges. Do not apply it during the search, or the comparisons will break.

From understanding to recall

You have just seen how binary search on the answer combines with inclusion-exclusion to solve Nth Magical Number in O(log(n * min(a, b))) time with O(1) space. The core idea is compact: count magical numbers up to x using x//a + x//b - x//lcm, then binary search for the smallest x where the count reaches n.

The tricky parts to internalize are the search bounds (start at min(a, b), end at n * min(a, b)), the direction of the binary search (search left when count >= n), and remembering to subtract the LCM term to avoid double-counting. These are easy to confuse under pressure. Spaced repetition helps you lock in the formula and the search template until writing them from scratch is automatic.

Binary search on the answer and inclusion-exclusion are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• Koko Eating Bananas - Another binary search on the answer problem
• Find First and Last Position of Element in Sorted Array - Classic binary search boundaries
• Split Array Largest Sum - Binary search on the answer with a greedy feasibility check