Nth Magical Number solution and explanation
Google
9 more videos on this problem
Nth Magical Number | Leetcode 878 | Binary SearchAyushi Sharma · 23:10 · 5K views
Leetcode 878(Hard) Nth Magical Number : Simple C++ SolutionShivam Patel · 9:39 · 3K views
Nth Magical Number | Leetcode 878 | Live coding session 🔥🔥🔥🔥 | Binary Search AlgoCoding Decoded · 12:31 · 3K views
Nth Magical Number | Google Interview Problem | Leetcode HardMay The Codes Be With You · 10:57 · 2K views
Nth Magical Number | LeetCode | Binary Search Explained in DetailTanishq Chaudhary · 16:10 · 1K views
Nth Magical Number | LeetCode 878 | Coders CampCoders Camp · 17:21 · 608 views
Leetcode [878] Nth Magical NumberSDE Skills · 22:06 · 461 views
Daily Leetcode #620: Dec 11, 2021 - 878. Nth Magical NumberProgramming Live with Larry · 23:11 · 371 views
878. Nth Magical Number | Leetcode 878 | Binary Search | Math | GFG | DSATejpratap Pandey · 25:54 · 369 views
878. Nth Magical Number || Leetcode || Amazon Interview QuestionTushar Goyal · 29:26 · 345 views
The problem
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 * 104
Approach overview
Problem 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 1: Binary Search Approach
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.
class Solution:
def nthMagicalNumber(self, n, a, b):
def gcd(x, y):
while y:
x, y = y, x % y
return x
def lcm(x, y):
return x * y // gcd(x, y)
LCM = lcm(a, b)
low, high = 2, n * min(a, b)
MOD = 10**9 + 7
while low < high:
mid = (low + high) // 2
if (mid // a + mid // b - mid // LCM) < n:
low = mid + 1
else:
high = mid
return low % MOD
# Example usage:
sol = Solution()
print(sol.nthMagicalNumber(4, 2, 3))class Solution {
public int nthMagicalNumber(int n, int a, int b) {
long MOD = 1000000007;
long left = 2, right = (long)n * Math.min(a, b);
long lcm_ab = lcm(a, b);
while (left < right) {
long mid = left + (right - left) / 2;
if (countMagicalNumbers(a, b, lcm_ab, mid) < n) {
left = mid + 1;
} else {
right = mid;
}
}
return (int)(left % MOD);
}
private long gcd(long a, long b) { return b == 0 ? a : gcd(b, a % b); }
private long lcm(long a, long b) { return a / gcd(a, b) * b; }
private long countMagicalNumbers(long a, long b, long lcm, long x) {
return x / a + x / b - x / lcm;
}
}#include <iostream>
#include <algorithm>
#define MOD 1000000007
using namespace std;
long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
long lcm(long a, long b) {
return (a / gcd(a, b)) * b;
}
int nthMagicalNumber(int n, int a, int b) {
long left = 2, right = (long)n * min(a, b);
long lcm_ab = lcm(a, b);
while (left < right) {
long mid = left + (right - left) / 2;
if ((mid / a + mid / b - mid / lcm_ab) < n)
left = mid + 1;
else
right = mid;
}
return left % MOD;
}
int main() {
int n = 4, a = 2, b = 3;
cout << nthMagicalNumber(n, a, b) << endl;
return 0;
}function nthMagicalNumber(n, a, b) {
const MOD = 1000000007;
function gcd(x, y) {
return y === 0 ? x : gcd(y, x % y);
}
function lcm(x, y) {
return (x * y) / gcd(x, y);
}
let lcm_ab = lcm(a, b);
let low = 2, high = n * Math.min(a, b);
while (low < high) {
let mid = Math.floor((low + high) / 2);
if (Math.floor(mid / a) + Math.floor(mid / b) - Math.floor(mid / lcm_ab) < n) {
low = mid + 1;
} else {
high = mid;
}
}
return low % MOD;
}
console.log(nthMagicalNumber(4, 2, 3));#include <stdio.h>
#define MOD 1000000007
long gcd(long a, long b) {
if (b == 0) return a;
return gcd(b, a % b);
}
long lcm(long a, long b) {
return (a / gcd(a, b)) * b;
}
int nthMagicalNumber(int n, int a, int b) {
long left = 2, right = (long)n * a;
long lcm_ab = lcm(a, b);
while (left < right) {
long mid = left + (right - left) / 2;
if ((mid / a + mid / b - mid / lcm_ab) < n)
left = mid + 1;
else
right = mid;
}
return (int)(left % MOD);
}
int main() {
int n = 4, a = 2, b = 3;
printf("%d\n", nthMagicalNumber(n, a, b));
return 0;
}using System;
class Solution {
public int NthMagicalNumber(int n, int a, int b) {
long MOD = 1000000007;
long left = 2, right = (long)n * Math.Min(a, b);
long lcm_ab = LCM(a, b);
while (left < right) {
long mid = left + (right - left) / 2;
if (CountMagicalNumbers(a, b, lcm_ab, mid) < n) {
left = mid + 1;
} else {
right = mid;
}
}
return (int)(left % MOD);
}
private long GCD(long a, long b) { return b == 0 ? a : GCD(b, a % b); }
private long LCM(long a, long b) { return a / GCD(a, b) * b; }
private long CountMagicalNumbers(long a, long b, long lcm, long x) {
return x / a + x / b - x / lcm;
}
}
class Program {
static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.NthMagicalNumber(4, 2, 3));
}
}In Python, the solution uses the binary search pattern efficiently within a while loop. Employing floor division ensures integers are handled correctly, while the counting of magical numbers utilizes the properties of GCD and LCM to adjust the range of the search space effectively.
Time Complexity: O(log(N * min(a, b)))
Space Complexity: O(1)
Approach 2: Min-Heap Based Approach
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.
import heapq
def nthMagicalNumber(n, a, b):
MOD = 10**9 + 7
lcm_ab = a * b // gcd(a, b)
heap = []
heapq.heappush(heap, a)
heapq.heappush(heap, b)
magical_number = 0
for _ in range(n):
magical_number = heapq.heappop(heap)
if not magical_number % a:
heapq.heappush(heap, magical_number + a)
if not magical_number % b:
heapq.heappush(heap, magical_number + b)
return magical_number % MOD
from math import gcd
# Example usage:
print(nthMagicalNumber(4, 2, 3))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 3: Default Approach
func nthMagicalNumber(n int, a int, b int) int {
c := a * b / gcd(a, b)
const mod int = 1e9 + 7
r := (a + b) * n
return sort.Search(r, func(x int) bool { return x/a+x/b-x/c >= n }) % mod
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}Complexity comparison
| 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 | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Nth Magical Number easy or hard?
Nth Magical Number is classified as Hard on LeetCode. The difficulty comes from recognizing that direct generation is inefficient and that the problem can be transformed into a counting function solved with binary search and LCM math.
Nth Magical Number Python/Java solution
Most implementations compute gcd, derive lcm(a,b), and perform binary search over the range [1, n * min(a,b)]. The same logic works in Python, Java, C++, C#, and JavaScript because it only uses integer arithmetic and loops.
How to solve Nth Magical Number in O(log n)?
Use binary search on the numeric range instead of generating numbers. For each midpoint, compute how many integers ≤ mid are divisible by a or b using inclusion-exclusion with LCM. Adjust the search range based on whether the count is smaller or larger than n until the smallest valid value is found.
What is the best approach for Nth Magical Number?
The optimal approach uses binary search combined with an LCM counting trick. For a candidate value x, count how many numbers ≤ x are divisible by a or b using x/a + x/b − x/lcm(a,b). Binary search finds the smallest x where this count is at least n. This runs in O(log(n * min(a,b))) time with constant space.
Is Nth Magical Number asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies like Google and Amazon because it combines number theory with binary search. It tests understanding of LCM, GCD, inclusion-exclusion, and searching over monotonic functions.
What data structure is used in Nth Magical Number?
The optimal solution does not require a complex data structure. It relies on mathematical counting with LCM and a binary search over integers. A min-heap can also be used in an alternative approach to generate multiples in sorted order.
What is the time complexity of Nth Magical Number?
The optimal binary search solution runs in O(log(n * min(a,b))) time because the search range is bounded by n * min(a,b). Each step performs constant-time arithmetic operations including gcd and division. Space complexity is O(1).