We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Convert to Base -2

Number: 1070

Difficulty: Medium

Paid? No

Companies: Airbnb

Problem Description

Given an integer n, convert it into its representation in base -2 and return the resulting binary string. The output should not have any leading zeros except if the answer is "0".

Key Insights

  • Use division and remainder operations to simulate converting a number to a different base.
  • When working with a negative base (-2), the remainder can become negative; adjust the remainder (by adding the base's absolute value) and update the quotient accordingly.
  • For n = 0, simply return "0" since there is nothing to convert.
  • Build the answer by collecting digits (remainders) and then reversing the order since the conversion provides digits from least significant to most significant.

Space and Time Complexity

Time Complexity: O(log|n|) – the loop runs for about the number of digits in the base -2 representation. Space Complexity: O(log|n|) – extra space for storing the computed digits.

Solution

To solve the problem, we simulate the conversion process similar to how you would convert an integer to a positive base. However, since the base here is -2, special handling of negative remainders is needed. In each iteration, we:

  1. Divide the current number by -2.
  2. Calculate the remainder. If the remainder is negative, adjust it by adding 2, and increment the quotient to compensate.
  3. Append the computed remainder to a list (which represents the binary digit).
  4. Continue until the number reduces to zero. Finally, reverse the list to form the correct string representation from the most significant to the least significant digit.

Code Solutions

Below are the code solutions in Python, JavaScript, C++, and Java.

# Python solution with detailed comments
def baseNeg2(n: int) -> str:
    # Special case for zero as input.
    if n == 0:
        return "0"
    
    digits = []  # List to store digits in base -2.
    
    while n != 0:
        n, remainder = divmod(n, -2)  # Get quotient and remainder when dividing by -2.
        if remainder < 0:
            # Adjust the remainder and increment the quotient.
            remainder += 2
            n += 1
        # Append the remainder (digit) to the list.
        digits.append(str(remainder))
    
    # Reverse the digits to form the proper binary string and return.
    return "".join(reversed(digits))

# Example usage:
print(baseNeg2(2))  # Output: "110"
print(baseNeg2(3))  # Output: "111"
print(baseNeg2(4))  # Output: "100"
← Back to All Questions