1017.Negative binary conversion

topic：

Give you an integer n ，Return to the integer in the form of a binary string Negative binary（base -2）express。

Notice，Unless the string is "0"，Otherwise, the returned string cannot contain the front guide zero。

 

Exemplary example 1：

enter：n = 2
Output："110"
explain：(-2)2 + (-2)1 = 2

Exemplary example 2：

enter：n = 3
Output："111"
explain：(-2)2 + (-2)1 + (-2)0 = 3

Exemplary example 3：

enter：n = 4
Output："100"
explain：(-2)2 = 4

 

hint：

• 0 <= n <= 109

Related Topics

math

👍 111

👎 0

[1017.Negative binary conversion.md]()

Thought：

We can judge n Every bit from low to high，If the bit is 1，Then the answer is 1，Otherwise 0。If the bit is 1，So we need to n minus k。Next we update n=⌊n/2⌋, k=−k。Continue to judge the next。
at last，We will return to the answer。
time complexity O(logn)，in n For the given integer。Ignore the space consumption of the answer，Spatial complexity O(1)。

Code：

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'