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 * 104This 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'.
C++
Java
Python
C#
JavaScript
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.
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) |
Find nth Magic Number | GeeksforGeeks • GeeksforGeeks • 19,844 views views
Watch 9 more video solutions →Practice Nth Magical Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor