{x}
blog image

Convert to Base -2

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".

 

Example 1:

Input: n = 2
Output: "110"
Explantion: (-2)2 + (-2)1 = 2

Example 2:

Input: n = 3
Output: "111"
Explantion: (-2)2 + (-2)1 + (-2)0 = 3

Example 3:

Input: n = 4
Output: "100"
Explantion: (-2)2 = 4

 

Constraints:

  • 0 <= n <= 109

Solution Explanation: Converting to Base -2

The problem asks to convert a given integer n into its base -2 representation. This isn't a standard base, so a typical base conversion algorithm won't work directly. The key is to understand how base -2 works.

Understanding Base -2

In base -2, the place values are powers of -2: ..., (-2)3, (-2)2, (-2)1, (-2)0. This means the place values alternate in sign: ..., -8, 4, -2, 1.

To represent a number in base -2, we find the coefficients (0 or 1) for each place value such that their sum equals the given number.

Algorithm

The algorithm iteratively subtracts the largest possible power of -2 that's less than or equal to the remaining value. We keep track of the coefficients (0 or 1) in a list, and finally reverse the list to get the correct base -2 representation.

  1. Initialization: Initialize k to 1 (representing (-2)0), an empty list ans to store the coefficients, and a variable to hold the current remainder.

  2. Iteration: While the current remainder n is not 0:

    • If n is odd (i.e., the least significant bit is 1), append '1' to ans and subtract k from n.
    • Otherwise (if n is even), append '0' to ans.
    • Divide n by 2 (integer division).
    • Multiply k by -1 to switch between positive and negative place values.

  3. Reversal and Output: Reverse the ans list and join its elements into a string. Handle the case where n is 0 to return "0".

Time and Space Complexity

  • Time Complexity: O(log n). The loop iterates approximately log2(n) times, as we are repeatedly dividing n by 2.

  • Space Complexity: O(log n). The ans list stores at most log2(n) digits.

Code Examples (Python)

The Python code directly implements this algorithm:

class Solution:
    def baseNeg2(self, n: int) -> str:
        k = 1
        ans = []
        while n:
            if n % 2:
                ans.append('1')
                n -= k
            else:
                ans.append('0')
            n //= 2
            k *= -1
        return ''.join(ans[::-1]) or '0'

This code efficiently converts the integer to base -2. The use of ans[::-1] provides a concise way to reverse the list. The or '0' handles the special case where n is initially 0. Other language examples follow a similar structure, adapting the syntax to their respective features.