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 <= 1092 <= a, b <= 4 * 104Problem 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.
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'.
Time Complexity: O(log(N * min(a, b)))
Space Complexity: O(1)
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.
Python
Time Complexity: O(n log n)
Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| Binary Search Approach | Time Complexity: O(log(N * min(a, b))) |
| Min-Heap Based Approach | Time Complexity: O(n log n) |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Min-Heap Generation | O(n log n) | O(n) | When learning the concept or generating the sequence directly |
| Binary Search with LCM Counting | O(log(n * min(a,b))) | O(1) | Optimal solution for large constraints and interview settings |
Nth Magical Number | Leetcode 878 | Binary Search • Ayushi Sharma • 5,388 views views
Watch 9 more video solutions →Practice Nth Magical Number with our built-in code editor and test cases.
Practice on FleetCode