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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Convert to Base -2

Difficulty: Medium

Problem Description

Given an integer n, return a binary string representing its representation in base -2. Note that the returned string should not have leading zeros unless the string is "0".

Key Insights

  • The base -2 representation allows both positive and negative powers of 2.
  • The conversion can be achieved using repeated division and mod operations.
  • The binary digits are generated in reverse order due to the nature of division.

Space and Time Complexity

Time Complexity: O(log n) - because the number of digits in the base -2 representation is proportional to the logarithm of n. Space Complexity: O(1) - as we are using a constant amount of space for variable storage.

Solution

To convert an integer n to its representation in base -2, we can use a method similar to converting to binary in positive bases. However, in base -2, the remainder can be negative, and we need to adjust accordingly. By repeatedly dividing the number by -2 and keeping track of the remainders, we can construct the binary representation. The result is built in reverse order.

Code Solutions

def baseNeg2(n):
    if n == 0:
        return "0"
    result = []
    while n != 0:
        n, remainder = divmod(n, -2)
        if remainder < 0:
            remainder += 2
            n += 1
        result.append(str(remainder))
    return ''.join(result[::-1])
← Back to All Questions