Nth Magical Number
HardPrompt
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: 2Example 2:
Input: n = 4, a = 2, b = 3
Output: 6
Constraints:
1 <= n <= 1092 <= a, b <= 4 * 104
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward and naive approach. We can simply iterate through all positive integers, starting from 1. For each integer, we check if it's a magical number (i.e., divisible by a or b). We use a counter to keep track of how many magical numbers we have found. When the counter reaches n, the current integer is our answer.
Algorithm
- Initialize a counter
countto 0 and a numbernumto 1. - Start an infinite loop.
- In each iteration, check if
numis divisible byaorb. - If it is, increment
count. - If
countbecomes equal ton, it meansnumis then-th magical number. Returnnum % (10^9 + 7). - If
countis not yetn, incrementnumand continue to the next iteration.
Walkthrough
The algorithm works by simulating the process of finding magical numbers one by one. It starts checking from num = 1. In a loop, it tests the condition num % a == 0 || num % b == 0. If this condition is true, we've found a magical number, so we increment a counter. We repeat this process, incrementing num each time, until our counter reaches the target n. The value of num at that point is the n-th magical number. While simple, its performance is directly tied to the magnitude of the final answer, which can be very large.
class Solution { public int nthMagicalNumber(int n, int a, int b) { long MOD = 1_000_000_007; long num = 1; int count = 0; while (count < n) { if (num % a == 0 || num % b == 0) { count++; } if (count == n) { return (int)(num % MOD); } num++; } return -1; // Should not be reached }}Complexity
Time
O(n * min(a, b)) - The n-th magical number can be as large as `n * min(a, b)`. The loop runs up to this value, making it prohibitively slow for large `n`.
Space
O(1) - Constant space is used as we only need a few variables to store the current number and the count.
Trade-offs
Pros
Very simple to understand and implement.
Requires minimal mathematical insight.
Cons
Extremely inefficient for large values of
n.Will result in a 'Time Limit Exceeded' (TLE) error on most platforms for the given constraints.
A more optimized approach than brute force is to generate the magical numbers directly instead of checking every integer. This can be viewed as merging two sorted lists: the list of multiples of a (a, 2a, 3a, ...) and the list of multiples of b (b, 2b, 3b, ...). We can maintain pointers to the current head of each list and, in each step, pick the smaller element, which is the next magical number in the combined sorted sequence.
Algorithm
- Initialize two pointers,
pAtoaandpBtob. These represent the next multiple ofaandbin their respective sequences. - Loop from 1 to
n. - In each iteration, determine the next magical number by comparing
pAandpB.- If
pA < pB, the next magical number ispA. UpdatepAto the next multiple:pA += a. - If
pB < pA, the next magical number ispB. UpdatepBto the next multiple:pB += b. - If
pA == pB, it's a common multiple. The magical number ispA. Advance both pointers:pA += aandpB += b.
- If
- After
niterations, the last found magical number is the answer. Return it modulo10^9 + 7.
Walkthrough
This method avoids checking non-magical numbers. We use two long variables, pA and pB, to keep track of the next available multiple of a and b. We loop n times. In each step, we find the minimum of pA and pB. This minimum is the next magical number. If they are equal, we've found a common multiple, which is counted as a single magical number. We then advance the pointer(s) that produced the minimum value. After n such steps, we will have found the n-th magical number.
class Solution { public int nthMagicalNumber(int n, int a, int b) { long MOD = 1_000_000_007; long pA = a; long pB = b; long magicalNum = 0; for (int i = 1; i <= n; i++) { if (pA < pB) { magicalNum = pA; pA += a; } else if (pB < pA) { magicalNum = pB; pB += b; } else { // pA == pB, a common multiple magicalNum = pA; pA += a; pB += b; } } return (int)(magicalNum % MOD); }}Complexity
Time
O(n) - The main loop runs exactly `n` times. This is a significant improvement but still insufficient for the given constraints.
Space
O(1) - Only a few variables are needed for the pointers and the result, so space is constant.
Trade-offs
Pros
Much more efficient than the brute-force approach.
Directly generates the required sequence without unnecessary checks.
Cons
The time complexity is linear with
n, which is too slow fornup to 10^9.Will also result in a 'Time Limit Exceeded' (TLE) error.
Since the sequence of magical numbers is monotonically increasing, we can use binary search to find the n-th term efficiently. The core idea is to search for the answer x in a range of possible values. For any given x, we need a way to quickly determine how many magical numbers are less than or equal to x. This can be done with a mathematical formula based on the Principle of Inclusion-Exclusion.
Algorithm
- First, create a helper function
gcd(x, y)to compute the Greatest Common Divisor using the Euclidean algorithm. - Calculate the Least Common Multiple (LCM) of
aandbusing the formulalcm = (a * b) / gcd(a, b). Uselongto prevent overflow. - The number of magical numbers less than or equal to some value
xis given by the Inclusion-Exclusion Principle:count(x) = x/a + x/b - x/lcm. - Perform a binary search on the possible range of answers. The lower bound
lowcan be 1, and a safe upper boundhighisn * min(a, b). - In each step of the binary search:
- Calculate
mid = low + (high - low) / 2. - Compute
count(mid). - If
count(mid) >= n, thenmidis a potential answer. We store it and try to find a smaller answer by settinghigh = mid - 1. - If
count(mid) < n, thenmidis too small, so we search in the upper half by settinglow = mid + 1.
- Calculate
- The loop terminates when
low > high, and the last valid answer found is then-th magical number. Return this answer modulo10^9 + 7.
Walkthrough
The number of integers up to x divisible by a is x/a. Similarly, for b, it's x/b. If we simply add these, x/a + x/b, we double-count the numbers divisible by both a and b. These are the multiples of the Least Common Multiple (LCM) of a and b. So, the correct count of magical numbers up to x is count(x) = x/a + x/b - x/lcm(a, b). With this count function, we can binary search for the smallest x such that count(x) is at least n. This x will be our n-th magical number.
class Solution { public int nthMagicalNumber(int n, int a, int b) { long MOD = 1_000_000_007; // Calculate LCM long longA = a; long longB = b; long commonDivisor = gcd(longA, longB); long lcm = (longA * longB) / commonDivisor; // Binary search for the answer long low = 1; long high = (long)n * Math.min(a, b); // A safe upper bound long ans = 0; while (low <= high) { long mid = low + (high - low) / 2; // Calculate how many magical numbers are <= mid long count = mid / a + mid / b - mid / lcm; if (count >= n) { ans = mid; // This is a potential answer high = mid - 1; // Try to find a smaller one } else { low = mid + 1; // mid is too small } } return (int)(ans % MOD); } // Helper function to compute GCD using Euclidean algorithm private long gcd(long x, long y) { while (y != 0) { long temp = y; y = x % y; x = temp; } return x; }}Complexity
Time
O(log(n * min(a, b))) - The binary search operates on a range up to `n * min(a, b)`. The GCD calculation is also logarithmic. This is very fast.
Space
O(1) - The algorithm uses a fixed amount of space regardless of the input size.
Trade-offs
Pros
Extremely efficient, with logarithmic time complexity.
The only approach that can pass the given constraints for large
n.
Cons
More complex to understand and implement compared to simulation.
Requires knowledge of number theory (GCD, LCM) and the binary search algorithm.
Solutions
Solution
class Solution { private static final int MOD = ( int ) 1 e9 + 7 ; public int nthMagicalNumber ( int n , int a , int b ) { int c = a * b / gcd ( a , b ); long l = 0 , r = ( long ) ( a + b ) * n ; while ( l < r ) { long mid = l + r >>> 1 ; if ( mid / a + mid / b - mid / c >= n ) { r = mid ; } else { l = mid + 1 ; } } return ( int ) ( l % MOD ); } private int gcd ( int a , int b ) { return b == 0 ? a : gcd ( b , a % b ); } }using ll = long long ; class Solution { public: const int mod = 1e9 + 7 ; int nthMagicalNumber ( int n , int a , int b ) { int c = lcm ( a , b ); ll l = 0 , r = 1ll * ( a + b ) * n ; while ( l < r ) { ll mid = l + r >> 1 ; if ( mid / a + mid / b - mid / c >= n ) r = mid ; else l = mid + 1 ; } return l % mod ; } };class Solution : def nthMagicalNumber ( self , n : int , a : int , b : int ) -> int : mod = 10 ** 9 + 7 c = lcm ( a , b ) r = ( a + b ) * n return bisect_left ( range ( r ), x = n , key = lambda x : x // a + x // b - x // c ) % modVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.