Skip to main content
Talentd

Nth Magical Number - Solution & Explanation

HardMathBinary Search11 min readAsked at: Amazon, Meta, Google
Practice this problem

Problem Statement

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

Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: n = 1, a = 2, b = 3
Output: 2

Example 2:

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

 

Constraints:

  • 1 <= n <= 109
  • 2 <= a, b <= 4 * 104

Approach Overview

Problem Overview: You need the n-th magical number, where a magical number is any integer divisible by a or b. The result can grow very large, so the final answer is returned modulo 1e9 + 7. The core challenge is counting how many numbers ≤ X are divisible by a or b efficiently.

Approach 1: Min-Heap Generation (O(n log n) time, O(n) space)

This approach generates magical numbers in increasing order using a min-heap. Start by pushing a and b into the heap and repeatedly extract the smallest value. Each time you pop a number, push its next multiple. A set or duplicate check is required because numbers like LCM(a,b) can appear from both sequences. After performing the extraction n times, the last popped value is the answer. The idea is similar to merging two sorted sequences of multiples. While easy to understand, heap operations make it slower for large n.

Approach 2: Binary Search with LCM Counting (O(log(n * min(a,b))) time, O(1) space)

This approach avoids generating numbers entirely. Instead, search for the smallest value x such that at least n magical numbers are ≤ x. Use binary search on the range [1, n * min(a,b)]. For any midpoint mid, compute how many numbers ≤ mid are divisible by a or b.

The key insight uses inclusion-exclusion from math. Numbers divisible by a are mid / a. Numbers divisible by b are mid / b. Numbers divisible by both are mid / lcm(a,b). So the total magical numbers ≤ mid is:

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

If count < n, move the search right; otherwise move left. The first value that satisfies the condition is the n-th magical number. Computing lcm(a,b) uses lcm = a * b / gcd(a,b). This method works because the count of valid numbers grows monotonically, which makes it ideal for binary search.

Recommended for interviews: Interviewers expect the binary search solution. The heap approach demonstrates understanding of ordered generation but does not scale well. Recognizing the counting trick with LCM and applying binary search shows strong problem-solving skills with number theory and monotonic search spaces.

Approach 1: Binary Search Approach

This approach leverages binary search to efficiently find the nth magical number by examining the number of magical numbers <= mid value repeatedly until we find the nth one. Calculating the Least Common Multiple (LCM) of 'a' and 'b' helps in determining magical numbers.

This solution defines functions to compute the Greatest Common Divisor (GCD) and the Least Common Multiple (LCM) which are used in the binary search. The search is done by iteratively halving the problem space until the nth magical number is found, which is tracked by counting the numbers <= mid divisible by either 'a' or 'b'.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log(N * min(a, b)))
Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Min-Heap Based Approach

This approach involves generating magical numbers using a min-heap to simulate the generation process by pushing candidates generated by multiplying a set of base magical numbers with 'a' and 'b'. The minimum is repeatedly extracted until the nth magical number is found.

The Python implementation uses a min-heap to manage and produce candidates for the magical numbers by systematically adding increments of 'a' and 'b'. The heap automatically keeps this collection sorted with respect to numerical magnitude, achieving efficient extraction. It ensures that duplicates (i.e., the same number coming from both sequences) are managed via conditions if a number is divisible by the increment.

Code

Python

Python

Complexity

Time Complexity: O(n log n)
Space Complexity: O(n)

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Binary Search Approach

Time Complexity: O(log(N * min(a, b)))
Space Complexity: O(1)

Min-Heap Based Approach

Time Complexity: O(n log n)
Space Complexity: O(n)

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Min-Heap GenerationO(n log n)O(n)When learning the concept or generating the sequence directly
Binary Search with LCM CountingO(log(n * min(a,b)))O(1)Optimal solution for large constraints and interview settings

Video Solution

Nth Magical Number | Leetcode 878 | Binary Search • Ayushi Sharma • 5,546 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Nth Magical Number easy or hard?
Nth Magical Number is classified as Hard on LeetCode. The difficulty comes from recognizing that direct generation is inefficient and that the problem can be transformed into a counting function solved with binary search and LCM math.
Nth Magical Number Python/Java solution
Most implementations compute gcd, derive lcm(a,b), and perform binary search over the range [1, n * min(a,b)]. The same logic works in Python, Java, C++, C#, and JavaScript because it only uses integer arithmetic and loops.
How to solve Nth Magical Number in O(log n)?
Use binary search on the numeric range instead of generating numbers. For each midpoint, compute how many integers ≤ mid are divisible by a or b using inclusion-exclusion with LCM. Adjust the search range based on whether the count is smaller or larger than n until the smallest valid value is found.
What is the best approach for Nth Magical Number?
The optimal approach uses binary search combined with an LCM counting trick. For a candidate value x, count how many numbers ≤ x are divisible by a or b using x/a + x/b − x/lcm(a,b). Binary search finds the smallest x where this count is at least n. This runs in O(log(n * min(a,b))) time with constant space.
Is Nth Magical Number asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Google and Amazon because it combines number theory with binary search. It tests understanding of LCM, GCD, inclusion-exclusion, and searching over monotonic functions.
What data structure is used in Nth Magical Number?
The optimal solution does not require a complex data structure. It relies on mathematical counting with LCM and a binary search over integers. A min-heap can also be used in an alternative approach to generate multiples in sorted order.
What is the time complexity of Nth Magical Number?
The optimal binary search solution runs in O(log(n * min(a,b))) time because the search range is bounded by n * min(a,b). Each step performs constant-time arithmetic operations including gcd and division. Space complexity is O(1).

Ready to solve this problem?

Practice Nth Magical Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer