Jobs

Interviews

Discussions

Base 7

Easy

Asked by:

69 views

Topics:

StringsRecursionBit Manipulation

Given an integer num, return a string of its base 7 representation.

Example 1:

Input: num = 100
Output: "202"

Example 2:

Input: num = -7
Output: "-10"

Constraints:

-10⁷ <= num <= 10⁷

Try coding it in LeetCode

Base 7

Easy

Asked by:

69 views

Topics:

StringsRecursionBit Manipulation

Given an integer num, return a string of its base 7 representation.

Example 1:

Input: num = 100
Output: "202"

Example 2:

Input: num = -7
Output: "-10"

Constraints:

-10⁷ <= num <= 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:

Can the input number be negative?
Is the input guaranteed to be within the range of a 32-bit integer?
Should I handle the case where the input is zero?
What data type should I return; a string, or an integer?
Are there any specific formatting requirements for the output string (e.g., leading zeros)?

Brute Force Solution

Approach

To convert a number to base 7 using brute force, we repeatedly find the remainders when dividing by 7. We then reconstruct the base 7 number from these remainders. Because we want to brute force this process, we will repeatedly check all possible combinations.

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

First, handle the case where the input is zero directly.
Next, determine if the number is negative and store this information.
If the number is negative, make it positive to simplify processing.
Repeatedly divide the (positive) number by 7, keeping track of the remainder after each division.
Continue this division process until the number becomes zero.
Take all the remainders we kept track of. These are the digits of the base 7 representation, but they are in reverse order.
Put the digits in the correct order. If the original number was negative, add a negative sign in front.

Code Implementation

def base7(number): 
    if number == 0:
        return "0"

    is_negative = number < 0

    # Work with the absolute value
    if is_negative:
        number = -number

    remainders = []
    while number > 0:
        remainders.append(number % 7)
        number //= 7

    # Remainders are in reverse order
    remainders.reverse()
    
    base_7_representation = "".join(map(str, remainders))

    # Add negative sign if necessary
    if is_negative:
        base_7_representation = "-" + base_7_representation

    return base_7_representation

Big(O) Analysis

Time Complexity

O(log n) – The dominant operation is repeatedly dividing the input number by 7 until it reaches zero. The number of divisions required is logarithmic with respect to the input number n, specifically log base 7 of n. Constructing the result string from the remainders takes time proportional to the number of digits, which is also logarithmic. Therefore, the overall time complexity is O(log n).

Space Complexity

O(log_7(abs(N))) – The algorithm stores the remainders in a data structure (implicitly a list or string builder) during the repeated division by 7. The number of remainders stored corresponds to the number of digits in the base 7 representation of the input number N. Since each division by 7 reduces the number's magnitude, the number of remainders, and thus the space used, is proportional to the base-7 logarithm of the absolute value of the input N (abs(N)). Therefore, the space complexity is O(log_7(abs(N))). Since the base of the logarithm is a constant, we can also express this as O(log(abs(N))).

Optimal Solution

Approach

Converting a number to base 7 is like repeatedly dividing by 7 and keeping track of the remainders. We essentially extract the 'digits' in base 7 one by one, starting from the least significant digit.

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

First, handle the special case when the number is zero. The base 7 representation of zero is simply '0'.
Next, determine if the number is negative. If it is, remember this fact and work with its absolute value.
Repeatedly divide the absolute value of the number by 7. The remainder of each division will be a digit in the base 7 representation.
Store these remainders. Since we're finding them from the least significant to the most significant, we'll need to reverse their order later.
Once the quotient becomes zero, we've extracted all the base 7 digits.
Reverse the order of the digits you stored.
If the original number was negative, add a minus sign to the beginning.
Finally, combine the digits into a string. This string is the base 7 representation of the original number.

Code Implementation

def convert_to_base7(number):    if number == 0:
        return "0"

    is_negative = number < 0
    absolute_number = abs(number)
    base7_digits = []

    # Extract base 7 digits
    while absolute_number > 0:
        remainder = absolute_number % 7
        base7_digits.append(str(remainder))
        absolute_number //= 7

    # Reverse digits for correct order
    base7_digits.reverse()

    # Add negative sign if needed
    if is_negative:
        base7_representation = "-" + "".join(base7_digits)
    else:
        base7_representation = "".join(base7_digits)

    return base7_representation

Big(O) Analysis

Time Complexity

O(log n) – The dominant operation is the repeated division of the input number n by 7 until the quotient becomes zero. The number of divisions required is proportional to the number of digits in the base 7 representation of n. Since each division reduces the number by a factor of 7, the number of divisions grows logarithmically with n. Therefore, the time complexity is O(log n), where n is the absolute value of the input number. Other operations like sign checking and string concatenation take constant time and are insignificant compared to the division process.

Space Complexity

O(log7|num|) – The algorithm stores the remainders of successive divisions by 7. In the worst case, the number of remainders (base 7 digits) is proportional to the logarithm base 7 of the absolute value of the input number, |num|. These remainders are stored in a temporary data structure (implicitly described as 'store these remainders'). Therefore, the auxiliary space used is proportional to log7|num|, which represents the number of digits in the base 7 representation. Thus, the space complexity is O(log7|num|).

Edge Cases

Case	How to Handle
Input is zero	Return "0" directly as the base 7 representation of zero is 0.
Input is a large positive integer close to maximum integer value	The algorithm uses integer division and modulo, which should handle large integers without overflow, within the limits of the language's integer type.
Input is a large negative integer close to minimum integer value	Handle negative numbers by storing the sign, converting to positive, processing the positive value, and prepending the negative sign.
Input is -1	Handle negative numbers correctly by converting to positive, processing, and then prepending a '-'.
Input is 1	Return "1" directly as the base 7 representation of 1 is 1.
Integer Overflow during conversion	Ensure the intermediate calculations (especially when handling large numbers) do not cause integer overflow; use long data type where appropriate to increase range.
Minimum Integer value as input	Taking the absolute value of the minimum integer can lead to overflow so handle this by special casing it or using a wider data type.
Repeated divisions resulting in very long base 7 representation	The algorithm's complexity is directly related to the number of digits in the base 7 representation which is logarithmic, so it scales well, but limit string builder size.

Input is zero

How to Handle:

Return "0" directly as the base 7 representation of zero is 0.

Input is a large positive integer close to maximum integer value

How to Handle:

The algorithm uses integer division and modulo, which should handle large integers without overflow, within the limits of the language's integer type.

Input is a large negative integer close to minimum integer value

How to Handle:

Handle negative numbers by storing the sign, converting to positive, processing the positive value, and prepending the negative sign.

Input is -1

How to Handle:

Handle negative numbers correctly by converting to positive, processing, and then prepending a '-'.

Input is 1

How to Handle:

Return "1" directly as the base 7 representation of 1 is 1.

Integer Overflow during conversion

How to Handle:

Ensure the intermediate calculations (especially when handling large numbers) do not cause integer overflow; use long data type where appropriate to increase range.

Minimum Integer value as input

How to Handle:

Taking the absolute value of the minimum integer can lead to overflow so handle this by special casing it or using a wider data type.

Repeated divisions resulting in very long base 7 representation

How to Handle:

The algorithm's complexity is directly related to the number of digits in the base 7 representation which is logarithmic, so it scales well, but limit string builder size.

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:

Can the input number be negative?
Is the input guaranteed to be within the range of a 32-bit integer?
Should I handle the case where the input is zero?
What data type should I return; a string, or an integer?
Are there any specific formatting requirements for the output string (e.g., leading zeros)?

Brute Force Solution

Approach

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

First, handle the case where the input is zero directly.
Next, determine if the number is negative and store this information.
If the number is negative, make it positive to simplify processing.
Repeatedly divide the (positive) number by 7, keeping track of the remainder after each division.
Continue this division process until the number becomes zero.
Take all the remainders we kept track of. These are the digits of the base 7 representation, but they are in reverse order.
Put the digits in the correct order. If the original number was negative, add a negative sign in front.

Code Implementation

def base7(number): 
    if number == 0:
        return "0"

    is_negative = number < 0

    # Work with the absolute value
    if is_negative:
        number = -number

    remainders = []
    while number > 0:
        remainders.append(number % 7)
        number //= 7

    # Remainders are in reverse order
    remainders.reverse()
    
    base_7_representation = "".join(map(str, remainders))

    # Add negative sign if necessary
    if is_negative:
        base_7_representation = "-" + base_7_representation

    return base_7_representation

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, handle the special case when the number is zero. The base 7 representation of zero is simply '0'.
Next, determine if the number is negative. If it is, remember this fact and work with its absolute value.
Repeatedly divide the absolute value of the number by 7. The remainder of each division will be a digit in the base 7 representation.
Store these remainders. Since we're finding them from the least significant to the most significant, we'll need to reverse their order later.
Once the quotient becomes zero, we've extracted all the base 7 digits.
Reverse the order of the digits you stored.
If the original number was negative, add a minus sign to the beginning.
Finally, combine the digits into a string. This string is the base 7 representation of the original number.

Code Implementation

def convert_to_base7(number):    if number == 0:
        return "0"

    is_negative = number < 0
    absolute_number = abs(number)
    base7_digits = []

    # Extract base 7 digits
    while absolute_number > 0:
        remainder = absolute_number % 7
        base7_digits.append(str(remainder))
        absolute_number //= 7

    # Reverse digits for correct order
    base7_digits.reverse()

    # Add negative sign if needed
    if is_negative:
        base7_representation = "-" + "".join(base7_digits)
    else:
        base7_representation = "".join(base7_digits)

    return base7_representation

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input is zero	Return "0" directly as the base 7 representation of zero is 0.
Input is a large positive integer close to maximum integer value	The algorithm uses integer division and modulo, which should handle large integers without overflow, within the limits of the language's integer type.
Input is a large negative integer close to minimum integer value	Handle negative numbers by storing the sign, converting to positive, processing the positive value, and prepending the negative sign.
Input is -1	Handle negative numbers correctly by converting to positive, processing, and then prepending a '-'.
Input is 1	Return "1" directly as the base 7 representation of 1 is 1.
Integer Overflow during conversion	Ensure the intermediate calculations (especially when handling large numbers) do not cause integer overflow; use long data type where appropriate to increase range.
Minimum Integer value as input	Taking the absolute value of the minimum integer can lead to overflow so handle this by special casing it or using a wider data type.
Repeated divisions resulting in very long base 7 representation	The algorithm's complexity is directly related to the number of digits in the base 7 representation which is logarithmic, so it scales well, but limit string builder size.

Input is zero

How to Handle:

Return "0" directly as the base 7 representation of zero is 0.

Input is a large positive integer close to maximum integer value

How to Handle:

The algorithm uses integer division and modulo, which should handle large integers without overflow, within the limits of the language's integer type.

Input is a large negative integer close to minimum integer value

How to Handle:

Handle negative numbers by storing the sign, converting to positive, processing the positive value, and prepending the negative sign.

Input is -1

How to Handle:

Handle negative numbers correctly by converting to positive, processing, and then prepending a '-'.

Input is 1

How to Handle:

Return "1" directly as the base 7 representation of 1 is 1.

Integer Overflow during conversion

How to Handle:

Ensure the intermediate calculations (especially when handling large numbers) do not cause integer overflow; use long data type where appropriate to increase range.

Minimum Integer value as input

How to Handle:

Taking the absolute value of the minimum integer can lead to overflow so handle this by special casing it or using a wider data type.

Repeated divisions resulting in very long base 7 representation

How to Handle:

The algorithm's complexity is directly related to the number of digits in the base 7 representation which is logarithmic, so it scales well, but limit string builder size.