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 * 104The key idea in #878 Nth Magical Number is to find the n-th number divisible by either of two integers. A direct simulation would be inefficient for large values, so the optimal approach relies on binary search combined with mathematical counting.
Instead of generating numbers, we search for the smallest value x such that there are at least n numbers less than or equal to x that are divisible by either of the given integers. Using the Least Common Multiple (LCM), we can avoid double-counting values divisible by both numbers. For any candidate value, we count how many valid numbers exist using a mathematical formula and adjust the binary search range accordingly.
This transforms the problem from enumeration to searching the answer space. The method is efficient even for very large constraints because each step halves the search range while using constant-time arithmetic operations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search with LCM-based Counting | O(log(N × min(a, b))) | O(1) |
GeeksforGeeks
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.
Time Complexity: O(log(N * min(a, b)))
Space Complexity: O(1)
1#include <stdio.h>
2#define MOD 1000000007
3
4long gcd(long a, long b) {
5 if (b == 0) return a;
6 return gcd(b, a % b);
7}
8
9long lcm(long a, long b) {
10 return (a / gcd(a, b)) * b;
11}
12
13int nthMagicalNumber(int n, int a, int b) {
14 long left = 2, right = (long)n * a;
15 long lcm_ab = lcm(a, b);
16 while (left < right) {
17 long mid = left + (right - left) / 2;
18 if ((mid / a + mid / b - mid / lcm_ab) < n)
19 left = mid + 1;
20 else
21 right = mid;
22 }
23 return (int)(left % MOD);
24}
25
26int main() {
27 int n = 4, a = 2, b = 3;
28 printf("%d\n", nthMagicalNumber(n, a, b));
29 return 0;
30}
31This 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'.
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.
Time Complexity: O(n log n)
Space Complexity: O(n)
1import heapq
2
3def nthMagicalNumber(n, a, b):
4
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this problem appear in interviews at large tech companies. It tests understanding of binary search on answer space, number theory concepts like LCM, and efficient counting strategies.
This problem does not rely on complex data structures. It primarily uses mathematical operations and binary search, along with computing the greatest common divisor (GCD) to derive the LCM.
The optimal approach uses binary search on the answer space combined with mathematical counting. By calculating how many numbers up to a candidate value are divisible by the given integers using LCM, we can efficiently determine whether we have reached the nth magical number.
LCM helps avoid double-counting numbers that are divisible by both given integers. When counting valid numbers up to a value, subtracting those divisible by the LCM ensures accurate inclusion-exclusion counting.
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.