Jobs

Interviews

Discussions

Smallest Good Base

Hard

Asked by:

39 views

Topics:

Binary SearchBit Manipulation

Given an integer n represented as a string, return the smallest good base of n.

We call k >= 2 a good base of n, if all digits of n base k are 1's.

Example 1:

Input: n = "13"
Output: "3"
Explanation: 13 base 3 is 111.

Example 2:

Input: n = "4681"
Output: "8"
Explanation: 4681 base 8 is 11111.

Example 3:

Input: n = "1000000000000000000"
Output: "999999999999999999"
Explanation: 1000000000000000000 base 999999999999999999 is 11.

Constraints:

n is an integer in the range [3, 10¹⁸].
n does not contain any leading zeros.

Try coding it in LeetCode

Smallest Good Base

Hard

Asked by:

39 views

Topics:

Binary SearchBit Manipulation

Given an integer n represented as a string, return the smallest good base of n.

We call k >= 2 a good base of n, if all digits of n base k are 1's.

Example 1:

Input: n = "13"
Output: "3"
Explanation: 13 base 3 is 111.

Example 2:

Input: n = "4681"
Output: "8"
Explanation: 4681 base 8 is 11111.

Example 3:

Input: n = "1000000000000000000"
Output: "999999999999999999"
Explanation: 1000000000000000000 base 999999999999999999 is 11.

Constraints:

n is an integer in the range [3, 10¹⁸].
n does not contain any leading zeros.

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 is the range of values for the input integer n?
Is the input integer n guaranteed to be greater than or equal to 2?
If no good base exists, what value should I return?
Are we looking for the smallest good base in terms of numerical value, or the number of digits in the base-k representation of n?
Is there a limit on the number of digits that a base-k representation of n can have?

Brute Force Solution

Approach

We want to find the smallest 'base' number that can be used to represent a given number using only 1s. The brute force approach involves trying every possible base and checking if it works.

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

Start by considering the smallest possible base, which is 2.
For each base, try to build the given number using only 1s in that base. For example, if the base is 3, we'd see if we can write the number as 1 + 3 + 9 + 27 + ... using only 1s.
If we can exactly represent the given number using only 1s with a certain base, then we have found a 'good' base.
Keep track of all the good bases you find.
Out of all the good bases, pick the smallest one. This is the smallest 'good base'.

Code Implementation

def smallest_good_base_brute_force(number_as_int):
    # Iterate through potential bases starting from 2
    for base_candidate in range(2, number_as_int):
        sum_of_powers = 0
        power_of_base = 1
        exponent = 0

        # Construct number from 1s in the current base
        while sum_of_powers < number_as_int:
            sum_of_powers += power_of_base
            power_of_base *= base_candidate
            exponent += 1

        # Check if the sum equals the number
        if sum_of_powers == number_as_int:
            return base_candidate

    # If no good base is found, the number - 1 is the smallest
    return number_as_int - 1

Big(O) Analysis

Time Complexity

O(log² n) – The algorithm iterates through potential lengths of the sequence of 1s, which is logarithmic with respect to the input number n. For each length, it performs a binary search to find the corresponding base. The binary search takes O(log n) time. Since the loop iterating through lengths also has a logarithmic bound, the overall time complexity becomes O(log n * log n), which is O(log² n).

Space Complexity

O(1) – The provided solution iterates through possible bases and for each base, checks if the given number can be represented using only 1s. The algorithm does not appear to use any auxiliary data structures like arrays, hash maps, or lists to store intermediate results or track visited bases. It seems to perform calculations in place, using a fixed number of variables regardless of the input number N. Therefore, the auxiliary space complexity is constant.

Optimal Solution

Approach

The challenge is to find the smallest number, let's call it 'k', such that a number 'n' can be expressed as a sum of powers of 'k'. The best approach involves cleverly searching for possible values of 'k' by first figuring out the possible number of terms in the sum and then narrowing down the search range to find the best 'k'.

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

Realize that if 'n' can be written as 1 + k + k^2 + ... + k^(m-1), then 'm', the number of terms, must be at least 2 because we need at least two numbers to sum up to 'n'. Also, 'm' cannot be greater than the logarithm (base 2) of 'n' plus 1 because even if k is 1, we can't have too many terms without the sum exceeding 'n'.
Iterate through possible values of 'm', starting from the largest possible value and going down to 2. The logic here is that if we have a larger number of terms, the base 'k' will be smaller, and we want the smallest possible 'k'.
For each value of 'm', perform a search to find the corresponding 'k'. Since 'k' must be an integer, we can use a binary search. The smallest possible value for 'k' is 2 (since it must be greater than 1) and the largest possible value for 'k' can be calculated based on the fact that k^(m-1) must be less than 'n'.
Inside the binary search, check if the sum 1 + k + k^2 + ... + k^(m-1) equals 'n'. If it does, then we have found a good base 'k' and we can stop. Return 'k' as a string.
If the sum is less than 'n', it means our guess for 'k' is too small, so we adjust the lower bound of the binary search.
If the sum is greater than 'n', it means our guess for 'k' is too large, so we adjust the upper bound of the binary search.
If we iterate through all possible values of 'm' from largest to smallest and can't find a 'k' that satisfies the equation, then the answer is simply 'n-1'. This is because n = 1 + 1 + 1 + ... + 1, with 'n' ones, can be expressed as (n-1)^1 + 1

Code Implementation

def smallestGoodBase(number):    number_as_integer = int(number)
    maximum_number_of_terms = number_as_integer.bit_length()
    for number_of_terms in range(maximum_number_of_terms, 1, -1):
        left_bound = 2
        right_bound = pow(number_as_integer, 1 / (number_of_terms - 1))

        while left_bound <= right_bound:
            potential_base = (left_bound + right_bound) // 2
            sum_of_powers = 0
            for i in range(number_of_terms):
                sum_of_powers += pow(potential_base, i)

            if sum_of_powers == number_as_integer:
                # We found a good base, return it as a string.
                return str(potential_base)
            elif sum_of_powers < number_as_integer:
                # The base is too small; increase the lower bound.
                left_bound = potential_base + 1
            else:
                # The base is too large; decrease the upper bound.
                right_bound = potential_base - 1
    # If no good base is found, n - 1 is always a good base.
    return str(number_as_integer - 1)

Big(O) Analysis

Time Complexity

O(log n * log n) – The algorithm iterates through possible values of 'm' (number of terms) from log2(n) down to 2. Inside the loop, a binary search is performed to find 'k'. The binary search has a range of at most n, so it takes O(log n) time. Since the outer loop also iterates a maximum of log2(n) times, the overall time complexity is approximately O(log n * log n).

Space Complexity

O(1) – The algorithm uses a binary search within a loop. The binary search uses a few variables to store the lower bound, upper bound, and middle value of the search range, along with a variable to accumulate the sum of powers of k. The outer loop iterates through possible values of m, but this iteration itself does not allocate additional memory that scales with the input n. The memory required for these variables remains constant regardless of the size of the input n. Therefore, the space complexity is O(1).

Edge Cases

Case	How to Handle
Input n is 1	Return -1 since 1 can't be a good base because (1^m + 1^(m-1) + ... + 1^0) always equals m+1, which can only be equal to 1 when m=0, and m must be >=1.
Input n is a power of 2	These cases often yield a base close to n-1 and should be handled efficiently by the search algorithm.
Integer overflow during base exponentiation	Use long data type for intermediate calculations and perform overflow checks during pow() operations by comparing the result with n / current_base.
Maximum possible input n (e.g., 10^18)	The binary search range for possible bases needs to be large enough to accommodate large n values and the solution must scale logarithmically to avoid TLE.
Cases where no good base exists	The binary search will converge to a low value; return the default value 'n-1' if no suitable base is found during search.
Base value equals 1	The loop can break and return n-1 immediately if current base being tested is 1.
The smallest possible base value 2 results in an exponent of 1	Ensure the initial value and bounds in the loop consider the scenario where only the largest potential exponent is used.
n is a prime number	The algorithm should still function correctly, potentially ending up testing base n-1 as that case can lead to the condition being met.

Input n is 1

How to Handle:

Return -1 since 1 can't be a good base because (1^m + 1^(m-1) + ... + 1^0) always equals m+1, which can only be equal to 1 when m=0, and m must be >=1.

Input n is a power of 2

How to Handle:

These cases often yield a base close to n-1 and should be handled efficiently by the search algorithm.

Integer overflow during base exponentiation

How to Handle:

Use long data type for intermediate calculations and perform overflow checks during pow() operations by comparing the result with n / current_base.

Maximum possible input n (e.g., 10^18)

How to Handle:

The binary search range for possible bases needs to be large enough to accommodate large n values and the solution must scale logarithmically to avoid TLE.

Cases where no good base exists

How to Handle:

The binary search will converge to a low value; return the default value 'n-1' if no suitable base is found during search.

Base value equals 1

How to Handle:

The loop can break and return n-1 immediately if current base being tested is 1.

The smallest possible base value 2 results in an exponent of 1

How to Handle:

Ensure the initial value and bounds in the loop consider the scenario where only the largest potential exponent is used.

n is a prime number

How to Handle:

The algorithm should still function correctly, potentially ending up testing base n-1 as that case can lead to the condition being met.

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 is the range of values for the input integer n?
Is the input integer n guaranteed to be greater than or equal to 2?
If no good base exists, what value should I return?
Are we looking for the smallest good base in terms of numerical value, or the number of digits in the base-k representation of n?
Is there a limit on the number of digits that a base-k representation of n can have?

Brute Force Solution

Approach

We want to find the smallest 'base' number that can be used to represent a given number using only 1s. The brute force approach involves trying every possible base and checking if it works.

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

Start by considering the smallest possible base, which is 2.
For each base, try to build the given number using only 1s in that base. For example, if the base is 3, we'd see if we can write the number as 1 + 3 + 9 + 27 + ... using only 1s.
If we can exactly represent the given number using only 1s with a certain base, then we have found a 'good' base.
Keep track of all the good bases you find.
Out of all the good bases, pick the smallest one. This is the smallest 'good base'.

Code Implementation

def smallest_good_base_brute_force(number_as_int):
    # Iterate through potential bases starting from 2
    for base_candidate in range(2, number_as_int):
        sum_of_powers = 0
        power_of_base = 1
        exponent = 0

        # Construct number from 1s in the current base
        while sum_of_powers < number_as_int:
            sum_of_powers += power_of_base
            power_of_base *= base_candidate
            exponent += 1

        # Check if the sum equals the number
        if sum_of_powers == number_as_int:
            return base_candidate

    # If no good base is found, the number - 1 is the smallest
    return number_as_int - 1

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Realize that if 'n' can be written as 1 + k + k^2 + ... + k^(m-1), then 'm', the number of terms, must be at least 2 because we need at least two numbers to sum up to 'n'. Also, 'm' cannot be greater than the logarithm (base 2) of 'n' plus 1 because even if k is 1, we can't have too many terms without the sum exceeding 'n'.
Iterate through possible values of 'm', starting from the largest possible value and going down to 2. The logic here is that if we have a larger number of terms, the base 'k' will be smaller, and we want the smallest possible 'k'.
For each value of 'm', perform a search to find the corresponding 'k'. Since 'k' must be an integer, we can use a binary search. The smallest possible value for 'k' is 2 (since it must be greater than 1) and the largest possible value for 'k' can be calculated based on the fact that k^(m-1) must be less than 'n'.
Inside the binary search, check if the sum 1 + k + k^2 + ... + k^(m-1) equals 'n'. If it does, then we have found a good base 'k' and we can stop. Return 'k' as a string.
If the sum is less than 'n', it means our guess for 'k' is too small, so we adjust the lower bound of the binary search.
If the sum is greater than 'n', it means our guess for 'k' is too large, so we adjust the upper bound of the binary search.
If we iterate through all possible values of 'm' from largest to smallest and can't find a 'k' that satisfies the equation, then the answer is simply 'n-1'. This is because n = 1 + 1 + 1 + ... + 1, with 'n' ones, can be expressed as (n-1)^1 + 1

Code Implementation

def smallestGoodBase(number):    number_as_integer = int(number)
    maximum_number_of_terms = number_as_integer.bit_length()
    for number_of_terms in range(maximum_number_of_terms, 1, -1):
        left_bound = 2
        right_bound = pow(number_as_integer, 1 / (number_of_terms - 1))

        while left_bound <= right_bound:
            potential_base = (left_bound + right_bound) // 2
            sum_of_powers = 0
            for i in range(number_of_terms):
                sum_of_powers += pow(potential_base, i)

            if sum_of_powers == number_as_integer:
                # We found a good base, return it as a string.
                return str(potential_base)
            elif sum_of_powers < number_as_integer:
                # The base is too small; increase the lower bound.
                left_bound = potential_base + 1
            else:
                # The base is too large; decrease the upper bound.
                right_bound = potential_base - 1
    # If no good base is found, n - 1 is always a good base.
    return str(number_as_integer - 1)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input n is 1	Return -1 since 1 can't be a good base because (1^m + 1^(m-1) + ... + 1^0) always equals m+1, which can only be equal to 1 when m=0, and m must be >=1.
Input n is a power of 2	These cases often yield a base close to n-1 and should be handled efficiently by the search algorithm.
Integer overflow during base exponentiation	Use long data type for intermediate calculations and perform overflow checks during pow() operations by comparing the result with n / current_base.
Maximum possible input n (e.g., 10^18)	The binary search range for possible bases needs to be large enough to accommodate large n values and the solution must scale logarithmically to avoid TLE.
Cases where no good base exists	The binary search will converge to a low value; return the default value 'n-1' if no suitable base is found during search.
Base value equals 1	The loop can break and return n-1 immediately if current base being tested is 1.
The smallest possible base value 2 results in an exponent of 1	Ensure the initial value and bounds in the loop consider the scenario where only the largest potential exponent is used.
n is a prime number	The algorithm should still function correctly, potentially ending up testing base n-1 as that case can lead to the condition being met.

Input n is 1

How to Handle:

Return -1 since 1 can't be a good base because (1^m + 1^(m-1) + ... + 1^0) always equals m+1, which can only be equal to 1 when m=0, and m must be >=1.

Input n is a power of 2

How to Handle:

These cases often yield a base close to n-1 and should be handled efficiently by the search algorithm.

Integer overflow during base exponentiation

How to Handle:

Use long data type for intermediate calculations and perform overflow checks during pow() operations by comparing the result with n / current_base.

Maximum possible input n (e.g., 10^18)

How to Handle:

The binary search range for possible bases needs to be large enough to accommodate large n values and the solution must scale logarithmically to avoid TLE.

Cases where no good base exists

How to Handle:

The binary search will converge to a low value; return the default value 'n-1' if no suitable base is found during search.

Base value equals 1

How to Handle:

The loop can break and return n-1 immediately if current base being tested is 1.

The smallest possible base value 2 results in an exponent of 1

How to Handle:

Ensure the initial value and bounds in the loop consider the scenario where only the largest potential exponent is used.

n is a prime number

How to Handle:

The algorithm should still function correctly, potentially ending up testing base n-1 as that case can lead to the condition being met.