Watch 10 video solutions for Nth Magical Number, a hard level problem involving Math, Binary Search. This walkthrough by Ayushi Sharma has 5,388 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |