# Given a number N, return a string consisting of "0"s and "1"s that represents its value in base -2 (negative two).
#
# The returned string must have no leading zeroes, unless the string is "0".
#
#
#
# Example 1:
#
# Input: 2
# Output: "110"
# Explantion: (-2) ^ 2 + (-2) ^ 1 = 2
# Example 2:
#
# Input: 3
# Output: "111"
# Explantion: (-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3
# Example 3:
#
# Input: 4
# Output: "100"
# Explantion: (-2) ^ 2 = 4


# Note:
# 0 <= N <= 10^9

class Solution(object):

    # let's firstly figure out how to change a decimail to binary, for ex, 19
    # divmod(19,2) = 9,1, res[0] = 1
    # divmod(9,2) = 4, 1  res[1] = 1
    # divmod(4,2) = 2, 0, res[2] = 0
    # divmod(2,2) = 1, 0  res[3] = 0
    # the last one we need to pick up the quotient instead of the reamin, so res[4] = 1
    # then res[::-1] 10011 is the final result => 16 + 2 + 1 = 19, confirm it was correct

    # but if base is -2
    # divmod(19,-2) = -9, 1, res[0] = 1 #knowledge the remain has to be positive
    # divmod(-9,-2) = 5, 1, res[1] = 1
    # divmod(5,-2) = -2, 1, res[2] = 1
    # divmod(-2,-2) = 1, 0, res[3]= 0, res[4] = 1
    # so we get 10111, (-2)**4 + (-2)**2 + (-2) + 1 = 16 + 4 - 2 + 1 = 19

    def baseNeg2(self, N):
        """
        :type N: int
        :rtype: str
        """
        res, n = '', N
        while n:
            if n < 0:
                # why we need to do (2-n) % 2? for ex, divmod(-9,-2), because the reminder need to be >= 0
                # -9/-2 = 4, -9 - (-2) * 4 = -1, this is not what we want, we need to have -9 -(-2) * 5 =1
                # so we do (2-(-9)) % 2 = 1
                r = (2 - n) % 2
                # the code is not elegant here, but I didn't find good way to do it
                # if r = 0,means n % 2 == 0, for divmod(-2,-2), we can get 1, 0, so for this case we don't
                # need (2-n), otherwise, such like (-9,-2), we need to do (2-(-9)/2 = 5
                n = (2 - n) >> 1 if r else (-n) >> 1
                res = str(r) + res
            elif n == 0:
                break
            else:
                # for ex, divmod(19,-2) = (19%2, -(19/2))
                r, n = n % 2, - (n >> 1)
                res = str(r) + res

        return res if res else '0'

    # For anyone who doesn't get the point, here is my explanation: In base 2 we multiply bits to 1, 2, 4, 8 ... to
    # get actual number in decimal. So for base -2, we need to multiply bits with 1, -2, 4, -8 ... to get number
    # in decimal. Therefore, we can use -(N >> 1)
    def baseNeg2_concise(self, x):
        res = []
        while x:
            res.append(x & 1)
            x = -(x >> 1)
        return "".join(map(str, res[::-1] or [0]))

    def baseNeg2_3(self, N):
        if N == 0:
            return '0'
        res = ''
        while N:
            rem = N % -2
            N //= -2
            if rem < 0:
                rem += 2
                N += 1
            res = str(rem) + res
        return res

if __name__ == '__main__':
    print Solution().baseNeg2(2)
    print Solution().baseNeg2(4)
    print Solution().baseNeg2(3)
