Jobs

Interviews

Discussions

Nth Magical Number

Hard

Nth Magical Number

Hard

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the upper bounds for `n`, `a`, and `b`? Should I be concerned about integer overflow during intermediate calculations?
Are `a` and `b` guaranteed to be positive integers?
If `n` is zero, what value should be returned?
If both `a` and `b` are equal, what would be the nth magical number? Would it be a * n?
Is there a constraint on the size of the output? For example, should I return the result modulo a specific number?

Brute Force Solution

Approach

We need to find the nth number that is divisible by either one number (let's call it A) or another number (let's call it B). The brute force way is just to start counting up from one and check each number one by one.

Here's how the algorithm would work step-by-step:

Start with the number one.
Check if the current number is divisible by A or B. If it is, it's a magical number.
If the number is magical, increase a counter of magical numbers found.
If the counter of magical numbers found is equal to n, then the current number is the nth magical number, so stop and give that number as the answer.
If the counter is not yet equal to n, increase the current number by one and go back to checking if it is divisible by A or B.
Repeat the above steps until the nth magical number is found.

Code Implementation

def find_nth_magical_number_brute_force(n, first_divisor, second_divisor):
    current_number = 0
    magical_number_count = 0

    while True:
        current_number += 1

        # Check if the current number is divisible by either divisor.
        if (current_number % first_divisor == 0) or (current_number % second_divisor == 0):
            magical_number_count += 1

            # If we've found the nth magical number, return it.
            if magical_number_count == n:
                return current_number

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates from 1 upwards, checking each number for divisibility by A or B until it finds the nth magical number. In the worst case, the nth magical number could be quite large, requiring us to check up to that number. Thus, the number of iterations is directly proportional to n, the desired index of the magical number. The divisibility checks themselves take constant time, so the overall time complexity is dominated by the iteration up to the nth magical number.

Space Complexity

O(1) – The provided algorithm uses a constant amount of extra space. It only stores a few integer variables: the current number being checked, a counter for magical numbers found, and the inputs A and B. The space used by these variables does not depend on the value of 'n'. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

This problem is about finding the nth number that is divisible by either of two given numbers. We will use a clever strategy based on binary search to efficiently find the answer without checking every number. This dramatically speeds up the process.

Here's how the algorithm would work step-by-step:

Realize that the answer must lie within a specific range of numbers. Establish the lower and upper bounds of that range.
Pick a number in the middle of that range. This is our guess.
Figure out how many numbers less than or equal to our guess are divisible by the first given number.
Figure out how many numbers less than or equal to our guess are divisible by the second given number.
Figure out how many numbers less than or equal to our guess are divisible by both given numbers. This helps avoid double-counting.
Add the first two counts together and subtract the last count to get the total number of magical numbers less than or equal to our guess.
Compare the total count to 'n'. If the count is less than 'n', our guess is too low, so search in the upper half of the range. If the count is greater than or equal to 'n', our guess is too high, so search in the lower half of the range.
Repeat the process of guessing and adjusting the range until we find the smallest number for which the total count is exactly 'n' or greater than or equal to 'n' after adjusting by subtracting the number that is divisible by both to get the correct 'nth' magical number.

Code Implementation

def nth_magical_number(n, a, b):
    modulo = 10**9 + 7

    least_common_multiple = (a * b) // gcd(a, b)

    low = min(a, b)
    high = n * min(a, b)

    while low < high:
        middle = (low + high) // 2

        # Calculate the number of magical numbers less than or equal to middle.
        count = (middle // a) + (middle // b) - (middle // least_common_multiple)

        # Adjust search range based on the count.
        if count < n:
            low = middle + 1
        else:
            high = middle

    # Ensure result is within constraints.
    return low % modulo

def gcd(a, b):
    #Euclidean Algorithm
    while b:
        a, b = b, a % b
    return a

Big(O) Analysis

Time Complexity

O(log(n)) – The solution uses binary search to find the nth magical number within a range. The search space is between 0 and max(a, b) * n, so the number of iterations in the binary search is logarithmic with respect to this range. Each iteration involves constant-time arithmetic operations and comparisons. Therefore, the time complexity is O(log(max(a, b) * n)), which simplifies to O(log(n)) assuming a and b are constants.

Space Complexity

O(1) – The provided algorithm uses binary search, which operates in place and does not create any auxiliary data structures that scale with the input 'n'. It uses a fixed number of variables to store the lower bound, upper bound, middle guess, and counts of magical numbers. Therefore, the space complexity is constant, independent of the value of 'n'.

Edge Cases

Case	How to Handle
n is zero	Return 0, as there is no 0th magical number by definition.
a or b is zero	If either a or b is zero, all multiples of the other will be magical numbers, so return n * (the non-zero number).
n is very large (approaching maximum integer value)	Use binary search with 64 bit integers to avoid overflow in calculations of high and mid values.
a and b are equal	All multiples of a (or b) will be magical numbers, so return n * a.
a or b is 1	The first n natural numbers are magical so return n.
LCM(a, b) is very large (close to the max integer value)	Pre-calculate LCM(a, b) using 64 bit integers to avoid overflow during binary search calculations and take mod before returning the answer.
a and b are prime numbers	The number of magical numbers up to 'mid' is mid/a + mid/b - mid/(a*b), which simplifies the calculation in the binary search.
Integer overflow when calculating mid/a, mid/b or mid/lcm during the binary search.	Use 64-bit integers for mid, a, b, and lcm to prevent integer overflows when performing the divisions.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the upper bounds for `n`, `a`, and `b`? Should I be concerned about integer overflow during intermediate calculations?
Are `a` and `b` guaranteed to be positive integers?
If `n` is zero, what value should be returned?
If both `a` and `b` are equal, what would be the nth magical number? Would it be a * n?
Is there a constraint on the size of the output? For example, should I return the result modulo a specific number?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the number one.
Check if the current number is divisible by A or B. If it is, it's a magical number.
If the number is magical, increase a counter of magical numbers found.
If the counter of magical numbers found is equal to n, then the current number is the nth magical number, so stop and give that number as the answer.
If the counter is not yet equal to n, increase the current number by one and go back to checking if it is divisible by A or B.
Repeat the above steps until the nth magical number is found.

Code Implementation

def find_nth_magical_number_brute_force(n, first_divisor, second_divisor):
    current_number = 0
    magical_number_count = 0

    while True:
        current_number += 1

        # Check if the current number is divisible by either divisor.
        if (current_number % first_divisor == 0) or (current_number % second_divisor == 0):
            magical_number_count += 1

            # If we've found the nth magical number, return it.
            if magical_number_count == n:
                return current_number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Realize that the answer must lie within a specific range of numbers. Establish the lower and upper bounds of that range.
Pick a number in the middle of that range. This is our guess.
Figure out how many numbers less than or equal to our guess are divisible by the first given number.
Figure out how many numbers less than or equal to our guess are divisible by the second given number.
Figure out how many numbers less than or equal to our guess are divisible by both given numbers. This helps avoid double-counting.
Add the first two counts together and subtract the last count to get the total number of magical numbers less than or equal to our guess.
Compare the total count to 'n'. If the count is less than 'n', our guess is too low, so search in the upper half of the range. If the count is greater than or equal to 'n', our guess is too high, so search in the lower half of the range.
Repeat the process of guessing and adjusting the range until we find the smallest number for which the total count is exactly 'n' or greater than or equal to 'n' after adjusting by subtracting the number that is divisible by both to get the correct 'nth' magical number.

Code Implementation

def nth_magical_number(n, a, b):
    modulo = 10**9 + 7

    least_common_multiple = (a * b) // gcd(a, b)

    low = min(a, b)
    high = n * min(a, b)

    while low < high:
        middle = (low + high) // 2

        # Calculate the number of magical numbers less than or equal to middle.
        count = (middle // a) + (middle // b) - (middle // least_common_multiple)

        # Adjust search range based on the count.
        if count < n:
            low = middle + 1
        else:
            high = middle

    # Ensure result is within constraints.
    return low % modulo

def gcd(a, b):
    #Euclidean Algorithm
    while b:
        a, b = b, a % b
    return a

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n is zero	Return 0, as there is no 0th magical number by definition.
a or b is zero	If either a or b is zero, all multiples of the other will be magical numbers, so return n * (the non-zero number).
n is very large (approaching maximum integer value)	Use binary search with 64 bit integers to avoid overflow in calculations of high and mid values.
a and b are equal	All multiples of a (or b) will be magical numbers, so return n * a.
a or b is 1	The first n natural numbers are magical so return n.
LCM(a, b) is very large (close to the max integer value)	Pre-calculate LCM(a, b) using 64 bit integers to avoid overflow during binary search calculations and take mod before returning the answer.
a and b are prime numbers	The number of magical numbers up to 'mid' is mid/a + mid/b - mid/(a*b), which simplifies the calculation in the binary search.
Integer overflow when calculating mid/a, mid/b or mid/lcm during the binary search.	Use 64-bit integers for mid, a, b, and lcm to prevent integer overflows when performing the divisions.