Jobs

Interviews

Discussions

Ugly Number III

Medium

Asked by:

4 views

Topics:

Binary Search

An ugly number is a positive integer that is divisible by a, b, or c.

Given four integers n, a, b, and c, return the n^th ugly number.

Example 1:

Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3^rd is 4.

Example 2:

Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4^th is 6.

Example 3:

Input: n = 5, a = 2, b = 11, c = 13
Output: 10
Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5^th is 10.

Constraints:

1 <= n, a, b, c <= 10⁹
1 <= a * b * c <= 10¹⁸
It is guaranteed that the result will be in range [1, 2 * 10⁹].

Try coding it in LeetCode

Ugly Number III

Medium

Asked by:

4 views

Topics:

Binary Search

An ugly number is a positive integer that is divisible by a, b, or c.

Given four integers n, a, b, and c, return the n^th ugly number.

Example 1:

Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3^rd is 4.

Example 2:

Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 10, 12... The 4^th is 6.

Example 3:

Input: n = 5, a = 2, b = 11, c = 13
Output: 10
Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5^th is 10.

Constraints:

1 <= n, a, b, c <= 10⁹
1 <= a * b * c <= 10¹⁸
It is guaranteed that the result will be in range [1, 2 * 10⁹].

Try coding it in LeetCode

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, b, and c? Specifically, what's the largest possible value for each of these integers?
Can a, b, or c be equal to 0 or 1? How should I handle those cases?
Do I need to worry about integer overflow when calculating multiples or performing intermediate calculations?
If n is very large and no ugly number can be found within a reasonable range due to extremely large a, b and c values, what value should I return?
Are a, b, and c guaranteed to be distinct, or could some of them be equal?

Brute Force Solution

Approach

The brute force approach to finding the nth ugly number involves checking every number, one by one, until we've found enough ugly numbers. We systematically test each number to see if it meets the 'ugly number' criteria.

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

Start with the number 1 and consider it as a potential ugly number.
Check if that number is divisible by any of the given prime factors. If it isn't, it's not an ugly number.
If the number is divisible by the prime factors, repeatedly divide the number by each prime factor until it's no longer divisible by any of them.
If the final result after dividing by all possible prime factors is 1, then the original number is an ugly number.
Keep track of how many ugly numbers we've found so far.
Move on to the next number and repeat the checking process.
Continue checking each number until we have found the required number of ugly numbers (n).

Code Implementation

def nth_ugly_number_brute_force(nth, first_prime, second_prime, third_prime):
    ugly_number_count = 0
    current_number = 0

    while ugly_number_count < nth:
        current_number += 1
        temporary_number = current_number

        # Repeatedly divide by each prime
        # factor until it's no longer divisible.
        while temporary_number % first_prime == 0:
            temporary_number //= first_prime

        while temporary_number % second_prime == 0:
            temporary_number //= second_prime

        while temporary_number % third_prime == 0:
            temporary_number //= third_prime

        # If the final result is 1, it's an ugly number
        if temporary_number == 1:
            ugly_number_count += 1

    return current_number

Big(O) Analysis

Time Complexity

O(n*log(m)) – To find the nth ugly number, the brute force approach iterates through numbers starting from 1 until we find n ugly numbers. For each number 'm', we check its divisibility by the given prime factors (a, b, c). In the worst case, we might need to repeatedly divide 'm' by these prime factors until it becomes 1 or is no longer divisible. The number of divisions in the while loops is logarithmic, specifically log base a, b, and c of m. Therefore, checking a single number 'm' takes O(log m) time where m is the potential ugly number being evaluated, and in the worst case, m will grow linearly with n. Since we need to find n such numbers, the overall time complexity is O(n * log(m)).

Space Complexity

O(1) – The provided algorithm checks each number one by one. It uses a constant number of variables (e.g., the current number being checked, counters) to track the progress and perform divisibility checks. No additional data structures such as arrays, lists, or hash maps are created or used. Therefore, the space required is constant regardless of the value of n, the number of ugly numbers we are searching for.

Optimal Solution

Approach

We need to find the nth number that's divisible by at least one of a given set of numbers. The trick is to efficiently count how many such numbers exist below a certain value, and then use this counting method to narrow down our search.

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

Think of it like a game of guessing a number. We'll start by guessing a number that we think might be close to the nth ugly number.
We need a way to count how many numbers smaller than our guess are divisible by at least one of the given numbers. We can find how many are divisible by each number individually. But we need to be careful not to double-count numbers divisible by more than one of the given numbers.
For example, if we have 2 and 3 as divisors, we add how many are divisible by 2 and how many are divisible by 3. But we must subtract how many are divisible by both 2 and 3 (i.e., divisible by 6) to correct for the double-counting.
We continue this process of adding and subtracting based on divisibility by combinations of the given numbers.
Now compare the count we computed with the number we're looking for (n). If the count is too small, our guess was too small. If the count is too large, our guess was too big.
Adjust our guess based on whether it was too big or too small. A good way to do this is to repeatedly bisect our search range by trying the middle value, until we find the smallest number whose count is equal to n.

Code Implementation

def ugly_number_iii(n, first_divisor, second_divisor, third_divisor):
    def count_ugly_numbers(value):
        # Use inclusion-exclusion principle.
        count = value // first_divisor + value // second_divisor + value // third_divisor
        count -= value // least_common_multiple(first_divisor, second_divisor)
        count -= value // least_common_multiple(first_divisor, third_divisor)
        count -= value // least_common_multiple(second_divisor, third_divisor)
        count += value // least_common_multiple(first_divisor, least_common_multiple(second_divisor, third_divisor))
        return count

    def least_common_multiple(first_number, second_number):
        return (first_number * second_number) // greatest_common_divisor(first_number, second_number)

    def greatest_common_divisor(first_number, second_number):
        while second_number:
            first_number, second_number = second_number, first_number % second_number
        return first_number

    low_value = 1
    high_value = 2 * 10**9

    while low_value < high_value:
        mid_value = low_value + (high_value - low_value) // 2

        # Count numbers divisible by at least one divisor
        count = count_ugly_numbers(mid_value)

        if count < n:
            low_value = mid_value + 1 # Guess was too low

        else:
            high_value = mid_value # Guess was too high, try lower

    # Binary search converges, 'low_value' is the nth ugly number
    return low_value

Big(O) Analysis

Time Complexity

O(log(N)) – The solution uses binary search to find the nth ugly number where N is the upper bound of the search space (e.g., 2 * 10^9). Inside the binary search loop, a count of ugly numbers less than or equal to the middle value is calculated using the inclusion-exclusion principle. The inclusion-exclusion principle involves iterating through all possible subsets of the given array of divisors, which has a time complexity exponential to the number of divisors. However, since the number of divisors is small and constant (typically 3 in the problem statement), this part can be considered constant time. Therefore, the dominant factor is the binary search, resulting in a time complexity of O(log(N)).

Space Complexity

O(1) – The algorithm primarily uses binary search and a counting function. The binary search involves updating variables like low, high, and mid, which require constant extra space. The counting function utilizes the inclusion-exclusion principle, potentially involving calculating the least common multiple (LCM) of subsets of the given numbers; however, the number of given numbers 'a', 'b', and 'c' is fixed (3), so the space required for calculating LCMs and intermediate counts remains constant. Therefore, the space complexity is independent of the search range or the target number 'n', resulting in O(1) auxiliary space.

Edge Cases

Case	How to Handle
n is 0 or negative	Return 0 or throw an exception, as there's no 0th or negative ugly number.
a, b, or c is 0	Division by zero error needs to be prevented, either by returning an appropriate error message or treating them as 1 since any number is divisible by 1.
n is a very large number (e.g., close to the maximum integer value)	The nth ugly number could be very large, potentially leading to integer overflow; use long integers to avoid this issue.
a, b, and c are all large prime numbers	The numbers will grow very quickly, potentially leading to inefficiencies if a binary search is used and the search space is too large, optimize the initial range of the binary search.
a, b, and c are all equal to 1	The first ugly number is 1, and all subsequent ugly numbers are also 1; return n.
a, b, and c have large common factors	The inclusion-exclusion principle should be used carefully to handle potential integer overflows during LCM calculations; use long data types for LCM.
n is 1	The smallest of a, b, and c will be the first ugly number; return min(a,b,c).
a, b, and c are all very small (e.g., 2, 3, 5)	The nth ugly number will not be very large, and the solution should perform efficiently, ensuring the binary search range is reasonably bounded to start.

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, b, and c? Specifically, what's the largest possible value for each of these integers?
Can a, b, or c be equal to 0 or 1? How should I handle those cases?
Do I need to worry about integer overflow when calculating multiples or performing intermediate calculations?
If n is very large and no ugly number can be found within a reasonable range due to extremely large a, b and c values, what value should I return?
Are a, b, and c guaranteed to be distinct, or could some of them be equal?

Brute Force Solution

Approach

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

Start with the number 1 and consider it as a potential ugly number.
Check if that number is divisible by any of the given prime factors. If it isn't, it's not an ugly number.
If the number is divisible by the prime factors, repeatedly divide the number by each prime factor until it's no longer divisible by any of them.
If the final result after dividing by all possible prime factors is 1, then the original number is an ugly number.
Keep track of how many ugly numbers we've found so far.
Move on to the next number and repeat the checking process.
Continue checking each number until we have found the required number of ugly numbers (n).

Code Implementation

def nth_ugly_number_brute_force(nth, first_prime, second_prime, third_prime):
    ugly_number_count = 0
    current_number = 0

    while ugly_number_count < nth:
        current_number += 1
        temporary_number = current_number

        # Repeatedly divide by each prime
        # factor until it's no longer divisible.
        while temporary_number % first_prime == 0:
            temporary_number //= first_prime

        while temporary_number % second_prime == 0:
            temporary_number //= second_prime

        while temporary_number % third_prime == 0:
            temporary_number //= third_prime

        # If the final result is 1, it's an ugly number
        if temporary_number == 1:
            ugly_number_count += 1

    return current_number

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Think of it like a game of guessing a number. We'll start by guessing a number that we think might be close to the nth ugly number.
We need a way to count how many numbers smaller than our guess are divisible by at least one of the given numbers. We can find how many are divisible by each number individually. But we need to be careful not to double-count numbers divisible by more than one of the given numbers.
For example, if we have 2 and 3 as divisors, we add how many are divisible by 2 and how many are divisible by 3. But we must subtract how many are divisible by both 2 and 3 (i.e., divisible by 6) to correct for the double-counting.
We continue this process of adding and subtracting based on divisibility by combinations of the given numbers.
Now compare the count we computed with the number we're looking for (n). If the count is too small, our guess was too small. If the count is too large, our guess was too big.
Adjust our guess based on whether it was too big or too small. A good way to do this is to repeatedly bisect our search range by trying the middle value, until we find the smallest number whose count is equal to n.

Code Implementation

def ugly_number_iii(n, first_divisor, second_divisor, third_divisor):
    def count_ugly_numbers(value):
        # Use inclusion-exclusion principle.
        count = value // first_divisor + value // second_divisor + value // third_divisor
        count -= value // least_common_multiple(first_divisor, second_divisor)
        count -= value // least_common_multiple(first_divisor, third_divisor)
        count -= value // least_common_multiple(second_divisor, third_divisor)
        count += value // least_common_multiple(first_divisor, least_common_multiple(second_divisor, third_divisor))
        return count

    def least_common_multiple(first_number, second_number):
        return (first_number * second_number) // greatest_common_divisor(first_number, second_number)

    def greatest_common_divisor(first_number, second_number):
        while second_number:
            first_number, second_number = second_number, first_number % second_number
        return first_number

    low_value = 1
    high_value = 2 * 10**9

    while low_value < high_value:
        mid_value = low_value + (high_value - low_value) // 2

        # Count numbers divisible by at least one divisor
        count = count_ugly_numbers(mid_value)

        if count < n:
            low_value = mid_value + 1 # Guess was too low

        else:
            high_value = mid_value # Guess was too high, try lower

    # Binary search converges, 'low_value' is the nth ugly number
    return low_value

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n is 0 or negative	Return 0 or throw an exception, as there's no 0th or negative ugly number.
a, b, or c is 0	Division by zero error needs to be prevented, either by returning an appropriate error message or treating them as 1 since any number is divisible by 1.
n is a very large number (e.g., close to the maximum integer value)	The nth ugly number could be very large, potentially leading to integer overflow; use long integers to avoid this issue.
a, b, and c are all large prime numbers	The numbers will grow very quickly, potentially leading to inefficiencies if a binary search is used and the search space is too large, optimize the initial range of the binary search.
a, b, and c are all equal to 1	The first ugly number is 1, and all subsequent ugly numbers are also 1; return n.
a, b, and c have large common factors	The inclusion-exclusion principle should be used carefully to handle potential integer overflows during LCM calculations; use long data types for LCM.
n is 1	The smallest of a, b, and c will be the first ugly number; return min(a,b,c).
a, b, and c are all very small (e.g., 2, 3, 5)	The nth ugly number will not be very large, and the solution should perform efficiently, ensuring the binary search range is reasonably bounded to start.