878. Nth Magical Number
Problem Description
The problem is about finding the n
th number that is divisible by at least one of the two given numbers, a
or b
. These kinds of numbers are referred to as magical numbers. For instance, if a
is 2 and b
is 3, then the first few magical numbers would be 2, 3, 4 (divisible by 2), 6 (divisible by both 2 and 3), 8 (divisible by 2), and so on. The function nthMagicalNumber
should return the n
th magical number in this sequence.
However, due to the potentially large size of the output, we don't want the exact value of the n
th magical number but instead its remainder when divided by 10^9 + 7
, which is a commonly used large prime number in modular arithmetic problems to prevent integer overflow errors.
Intuition
When solving this problem, we need to consider a vital property of lcm (Least Common Multiple) of a
and b
, which will further help us understand the distribution of magical numbers. Specifically, every multiple of the lcm of a
and b
is a magical number which is also the least common period in which all the magical numbers repeat.
To arrive at the solution, we observe that:
- Each multiple of
a
is a magical number. - Each multiple of
b
is a magical number. - Some numbers are multiples of both
a
andb
, specifically multiples of the lcm ofa
andb
.
We use a binary search to find the smallest number x
where the count of magical numbers up to x
is at least n
. To count the number of magical numbers up to x
, we sum up x // a
(the count of multiples of a
up to x
), x // b
(the count of multiples of b
up to x
), and subtract x // c
(to account for over-counting the numbers that are multiples of both a
and b
, hence multiples of their lcm c
).
The code exploits the bisect_left
function from the bisect
module to perform the binary search efficiently. It passes a virtual sequence up to r = (a + b) * n
(an upper bound for the nth magical number) to bisect_left
with a custom key function that calculates the aforementioned count. Then, it takes the result x
of the binary search, which is essentially the n
th magical number, and applies the modulo to maintain the result within the bounds required by the problem statement.
Learn more about Math and Binary Search patterns.
Solution Approach
The implementation of the solution includes the following concepts:
-
Binary Search: A classical algorithm to find the position of an element in a sorted array in logarithmic time complexity. Here, it is used to find the smallest number
x
such that there are at leastn
magical numbers less than or equal tox
. -
Least Common Multiple (LCM): Used to calculate the period at which the multiples of
a
andb
repeat. This is critical, as we must adjust the counts to avoid counting any number more than once if it is divisible by botha
andb
. -
Modular Arithmetic: This is used to avoid large number overflows by taking the modulus of the result with
10**9 + 7
. -
Efficient Counting: Using integer division to count multiples up to
x
fora
,b
, and their lcm.
Looking at the implementation step-by-step:
- The
mod
variable is set to10**9 + 7
to prepare for the final output to be given modulo this large prime. - The variable
c
calculates the lcm ofa
andb
using a built-inlcm
function (not shown in the snippet given, but can be implemented as the product ofa
andb
divided by their greatest common divisor (gcd)). - The variable
r
defines an upper bound for then
th magical number, which can be set as the sum ofa
andb
multiplied byn
. This is based on the assumption that magical numbers will appear frequently enough that we do not need to check any number greater than this bound. - The magic happens with
bisect_left(range(r), x=n, key=lambda x: x // a + x // b - x // c)
. This call is a bit unusual because it usesbisect_left
on a range, leveraging the fact that Python ranges are lazy (they do not instantiate all values) and thus can be enormous without using much memory. The key function calculates the count of magical numbers up tox
, andbisect_left
will find the position where this count reaches at leastn
. - The
% mod
at the end of the function ensures the result is within the required modulus to prevent overflow and match the problem's constraints.
In summary, the code uses a binary search to efficiently find the n
th magical number, leveraging knowledge of mathematical properties and algorithmic patterns to do so within the computing constraints.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach with an example, let's choose a = 2
, b = 3
, and we want to find the 5
th magical number.
Following the given solution approach:
-
Calculate the least common multiple (LCM) of
a
andb
. The LCM of 2 and 3 is 6, because 6 is the smallest number that is divisible by both 2 and 3. Therefore, every 6 steps, the pattern of magical numbers will repeat. -
We set an upper bound for the binary search. For
n
magical numbers, a rough upper bound would be(a+b) * n
. In this case,(2+3)*5 = 25
. Therefore, we can start our binary search from1
to25
. -
Use a binary search to find the smallest number
x
such that there are at leastn
magical numbers less than or equal tox
. We do this by checking the count of multiples ofa
andb
subtracted by the count of their LCM up to certainx
. For each candidate numberx
, we calculate the count asx // a + x // b - x // c
, wherec
is the LCM. -
Suppose we test
x = 10
. To count the magic numbers up to 10, we find:- Multiples of 2 up to 10:
10 // 2 = 5
(2, 4, 6, 8, 10). - Multiples of 3 up to 10:
10 // 3 = 3
(3, 6, 9). - Multiples of 6 up to 10:
10 // 6 = 1
(6).
Now we sum the counts of multiples of
a
andb
then subtract the count of LCM ofa
andb
:5 + 3 - 1 = 7
. This means there are 7 magical numbers up to 10. Since we are looking for the 5th magical number, 10 is an upper bound (too high) and we need to search lower. - Multiples of 2 up to 10:
-
Adjust the binary search range accordingly. Let's try
x = 8
. The calculations give us:- Multiples of 2 up to 8:
8 // 2 = 4
(2, 4, 6, 8). - Multiples of 3 up to 8:
8 // 3 = 2
(3, 6). - Multiples of 6 up to 8:
8 // 6 = 1
(6).
Summing up and subtracting gives us
4 + 2 - 1 = 5
. There are 5 magical numbers up to 8, so 8 is our candidate for the 5th magical number. - Multiples of 2 up to 8:
-
Repeat the binary search process until the range is narrowed down to a single number. Since we already found that there are 5 magical numbers up to 8 and we are looking for the 5th magical number, we can conclude that 8 is the 5th magical number.
-
Finally, we apply the modulo operation. Since the number is lower than
10**9 + 7
, the modulus doesn't change the number. So the5
th magical number givena = 2
andb = 3
is8
.
This example demonstrates the binary search-based approach in a clear and step-by-step manner, following the key concepts outlined in the initial solution approach.
Solution Implementation
1from math import gcd
2from bisect import bisect_left
3
4class Solution:
5 def nth_magical_number(self, n: int, a: int, b: int) -> int:
6 # Define the modulo for the result as per the problem statement.
7 MOD = 10**9 + 7
8
9 # Function to calculate the least common multiple (LCM).
10 def lcm(x, y):
11 return x * y // gcd(x, y)
12
13 # Calculate the least common multiple of a and b.
14 lcm_of_a_b = lcm(a, b)
15
16 # Calculate an upper boundary for the search space (this is not tight).
17 r = (a + b) * n
18
19 # Use binary search to find the nth magical number.
20 # The key function calculates the number of magical numbers
21 # less than or equal to 'x' by summing the number of multiples of 'a' and 'b',
22 # then subtracting the number of multiples of 'lcm_of_a_b' to avoid double counting.
23 nth_magical = bisect_left(range(r), n, key=lambda x: x // a + x // b - x // lcm_of_a_b)
24
25 # Return the nth magical number modulo MOD.
26 return nth_magical % MOD
27
1class Solution {
2 // Define modulus constant for the problem
3 private static final int MOD = (int) 1e9 + 7;
4
5 // Function to find the nth magical number
6 public int nthMagicalNumber(int n, int a, int b) {
7 // Calculate least common multiple of a and b using gcd (Greatest Common Divisor)
8 int leastCommonMultiple = a * b / gcd(a, b);
9
10 // Initialize binary search bounds
11 long lowerBound = 0;
12 long upperBound = (long) (a + b) * n;
13
14 // Binary search to find the smallest number that is the nth magical number
15 while (lowerBound < upperBound) {
16 // Middle of the current bounds
17 long mid = (lowerBound + upperBound) >>> 1;
18
19 // Check if the mid number is a valid magical number by counting
20 // all multiples of a and b up to mid, minus those of their lcm to avoid double-counting
21 if (mid / a + mid / b - mid / leastCommonMultiple >= n) {
22 // If count is equal or greater than n, we shrink the right bound
23 upperBound = mid;
24 } else {
25 // Otherwise, we need to look for a larger number
26 lowerBound = mid + 1;
27 }
28 }
29
30 // After binary search, lower bound is our nth magical number
31 // Return it modulo MOD
32 return (int) (lowerBound % MOD);
33 }
34
35 // Utility method to calculate the greatest common divisor using Euclid's algorithm
36 private int gcd(int a, int b) {
37 // Recursive calculation of gcd
38 return b == 0 ? a : gcd(b, a % b);
39 }
40}
41
1#include <numeric> // Include necessary library for std::lcm
2
3class Solution {
4public:
5 const int MOD = 1e9 + 7; // Use uppercase for constants
6
7 int nthMagicalNumber(int n, int a, int b) {
8 int lcm_ab = std::lcm(a, b); // Calculate the least common multiple of a and b
9 long long left = 0, right = 1LL * (a + b) * n; // Use long long for large ranges
10
11 // Perform a binary search to find the nth magical number
12 while (left < right) {
13 long long mid = (left + right) / 2; // Calculate the middle value
14 // Check if the mid value has n or more multiples of a or b, considering overlaps
15 if (mid / a + mid / b - mid / lcm_ab >= n)
16 right = mid; // Too high, decrease right
17 else
18 left = mid + 1; // Too low, increase left
19 }
20
21 return left % MOD; // Return the nth magical number modulo MOD
22 }
23};
24
1function lcm(a: number, b: number): number {
2 // Calculate the greatest common divisor (GCD) using Euclid's algorithm
3 function gcd(a: number, b: number): number {
4 while (b !== 0) {
5 let t = b;
6 b = a % b;
7 a = t;
8 }
9 return a;
10 }
11
12 // Calculate the least common multiple (LCM) using the relationship between GCD and LCM
13 return (a * b) / gcd(a, b);
14}
15
16const MOD: number = 1e9 + 7; // Use uppercase for constants
17
18function nthMagicalNumber(n: number, a: number, b: number): number {
19 // Calculate the least common multiple of a and b
20 let lcmAB: number = lcm(a, b);
21 let left: number = 0, right: number = (a + b) * n; // Use `number` type for the range
22
23 // Perform a binary search to find the nth magical number
24 while (left < right) {
25 let mid: number = Math.floor((left + right) / 2); // Calculate the middle value
26
27 // Check if the mid value has n or more multiples of a or b, considering overlaps
28 if (Math.floor(mid / a) + Math.floor(mid / b) - Math.floor(mid / lcmAB) >= n)
29 right = mid; // Too high, adjust the right boundary
30 else
31 left = mid + 1; // Too low, adjust the left boundary
32 }
33
34 // Return the nth magical number modulo MOD
35 return left % MOD;
36}
37
38// Usage
39// let result = nthMagicalNumber(n, a, b); // Invoke the function with desired values of n, a, and b
40
Time and Space Complexity
Time Complexity
The given code snippet finds the n
th magical number where a magical number is a number divisible by either a
or b
.
To analyze the time complexity, let's consider the operations performed:
-
Calculating the least common multiple (lcm) of
a
andb
. The time complexity of finding the lcm depends on the algorithm used. If the Euclidean algorithm is used to find the gcd (greatest common divisor), then this part of the code has a time complexity ofO(log(min(a, b))
. -
The
bisect_left
function performs a binary search. The parameterrange(r)
has a length of aboutNx(a+b)/lcm(a,b)
. The binary search algorithm has a time complexity ofO(log n)
, but since it's not searching through a simple list but using a lambda function to generate values on the fly, the key function is calculated for every middle element in each iteration of the binary search. This, therefore, results in a time complexity ofO(log(Nx(a+b)/lcm(a,b)) * log(min(a, b)))
because each key calculation isO(log(min(a, b)))
. -
The modulo operation is constant time,
O(1)
.
Given these points, the overall time complexity is O(log(Nx(a+b)/lcm(a,b)) * log(min(a, b)))
.
Space Complexity
The code uses a constant amount of extra space:
- Storing variables such as
mod
,c
, andr
requiresO(1)
space. - The
bisect_left
function does not create additional data structures that scale with the input size, since the range does not actually create a list but is an iterator.
The lambda function within bisect_left
is stateless and does not consume more memory proportional to the size of the input. Therefore, the overall space complexity of the provided function is O(1)
(constant space).
Learn more about how to find time and space complexity quickly using problem constraints.
How many times is a tree node visited in a depth first search?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!