Problem:
 Score : 300 points    Problem Statement Given an integer N , find the base -2 representation of N .  Here, S is the base -2 representation of N when the following are all satisfied:   S is a string consisting of 0 and 1 .  Unless S =  0 , the initial character of S is 1 .  Let S = S_k S_{k-1} ... S_0 , then S_0 \times (-2)^0 + S_1 \times (-2)^1 + ... + S_k \times (-2)^k = N .   It can be proved that, for any integer M , the base -2 representation of M is uniquely determined.      Constraints  Every value in input is integer.  -10^9 \leq N \leq 10^9         Input Input is given from Standard Input in the following format:  N       Output Print the base -2 representation of N .        Sample Input 1 -9      Sample Output 1 1011  As (-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9 , 1011 is the base -2 representation of -9 .       Sample Input 2 123456789      Sample Output 2 11000101011001101110100010101       Sample Input 3 0      Sample Output 3 0

Solution (Python):
N = int(input())
ans =""
while not (N == 0):
    if not int((N%2))==0:
        N -= 1
        ans = '1' + ans
    else:
        ans = "0" + ans
    N = int(N/-2)
if ans == "": ans = "0"

print(ans)

Solution (Python):
N =int(input().strip())

target = N
output_str = ""

while target != 0:
    if target % 2 == 1:
        output_str = "1" + output_str
        target = (target - 1) / (-2)
    else:
        output_str = "0" + output_str
        target = (target) / (-2)

if output_str != "" :
    print(output_str)
else:
    print("0")

Solution (Python):
N = int(input())
i = 0
str = ""

if N == 0:
  print('0')
  exit(0)

while(N != 0):
  if N % 2 == 1:
    str = '1' + str
    N = N - 1
  else:
    str = '0' + str
  
  N = N // (-2)
  

print(str)

Solution (Python):
n=int(input())
string=""

if n==0:
    string="0"
while n!=0:
    if n%2==1:
        string="1"+string
        n=n-1
    else:
        string="0"+string
    n=n//(-2)
    
print(string)

Solution (Python):
if __name__ == "__main__":
    N = int(input())
    for bit in range(0, 1 << 20):
        ans = "0" * 64
        ans = list(ans)
        res = 0

        base = 1
        idx = 0
        tmp_bit = bit
        while (tmp_bit > 0):
            if tmp_bit % 2 != 0:
                res += base
                ans[idx] = '1'
            tmp_bit = tmp_bit >> 1
            base *= 4
            idx += 2
        if N > res:
            continue
        
    
        for x in range(41, 0, -2):
            base = 2 ** x
            base *= -1
            if res + base >= N:
                res += base
                ans[x] = '1'
        if res == N:
            ans = "".join(reversed(ans))
            for i in range(len(ans)):
                if ans[i] == '1':
                    print (ans[i:])
                    exit(0)
            print (0)
            exit(0)

Solution (Python):
n=int(input())
ansarr=''
while n != 0:
    q=n//(-2)
    r=n % (-2)
    
    if(r==-1): 
        r=1
        q+=1
    ansarr+=str(r)
    n=q
    
if(ansarr == ''):
    ansarr = '0'
else:
    ansarr = ansarr[::-1]
print(ansarr)

Solution (Python):
N = int(input())
ans = ''
while N != 0:
    bit = N % 2
    ans = str(bit) + ans
    N -= bit
    N //= -2
if not ans:ans=0
print(ans)

Solution (Python):
n = int(input())
ret = ''
while n != 0:
  d, r = n // (-2), n % (-2)
  if r == -1: 
    r = 1
    d += 1
  ret += str(r)
  n = d
if ret == '':
  ret = '0'
else:
  ret = ret[::-1]
print(ret)

Solution (Python):
N=int(input())
S=""
if N==0:
    print(0)
    exit()
while(True):
    if N==1:
        S="1"+S
        break
    if N%2==1:
        S="1"+S
    else:
        S="0"+S
    N-=N%2
    N=N//(-2)
print(S)

Solution (Python):
N = int(input())
if N == 0:
    print(0)
    exit()

ans = ''
while N != 1:
    if N%2:
        N -= 1
        ans += '1'
    else:
        ans += '0'
    N //= -2
ans += '1'
print(ans[::-1])

Solution (Python):
n = int(input())

ans=""

while(n!=0):
  if(n%2==0):
    ans = "0"+ans 
  else:
    n=n-1
    ans = "1"+ans
  n= n/-2

if(ans==""):
  ans="0"

print(ans)

Solution (Python):
n = int(input())
s = ''
while n:
  x = (n + 40000000000) % 4
  if x == 0:
    s = '00' + s
  if x == 1:
    s = '01' + s
    n -= 1
  if x == 2:
    s = '10' + s
    n += 2
  if x == 3:
    s = '11' + s
    n += 1
  n //= 4
s = s.lstrip('0')
if not s:
  s = '0'
print(s)

Solution (Python):
from math import floor, ceil, log

N = int(input())


def base10to(n, b):
    if n // b > 0:
        return base10to(n // b, b) + str(n % b)
    else:
        return str(n % b)

def calc_base_for_pos_N(N):
    S_base4 = base10to(N, 4) 

    S_raw = list(map(int, tuple(''.join([digit + '0' for digit in S_base4])[:-1])))[::-1]

    
    position = 0
    while position <= len(S_raw) - 3:
        digit = S_raw[position]
        
        if position % 2 == 1:
            position += 1
            continue
        if digit in {0, 1}:
            position += 1
            continue
        elif digit == 2:
            S_raw[position] = 0
            S_raw[position + 1] += 1
            S_raw[position + 2] += 1
        elif digit == 3:
            S_raw[position] = 1
            S_raw[position + 1] += 1
            S_raw[position + 2] += 1
        else: 
            S_raw[position] = 0
            S_raw[position + 2] += 1
        position += 2

    
    if S_raw[-1] == 2:
        S_raw[-1] = 0
        S_raw += [1, 1]
    elif S_raw[-1] == 3:
        S_raw[-1] = 1
        S_raw += [1, 1]
    elif S_raw[-1] == 4:
        S_raw[-1] = 0
        S_raw += [0, 1]

    S = ''.join([str(digit) for digit in S_raw])[::-1]
    return S

if N >= 0:
    print(calc_base_for_pos_N(N))
else:
    pos_N = abs(N)
    pos_S = list(map(int, list(calc_base_for_pos_N(pos_N))))
    pos_S = pos_S[::-1]
    shifted_S = [0] + pos_S
    pos_S = pos_S + [0]
    assert len(pos_S) == len(shifted_S)
    S_raw = [shifted_S[i] + pos_S[i] for i in range(len(pos_S))]
    position = 0
    while position <= len(S_raw) - 3:
        digit = S_raw[position]
        if digit in {0, 1}:
            position += 1
            continue
        elif digit == 2:
            S_raw[position] = 0
            S_raw[position + 1] += 1
            S_raw[position + 2] += 1
        elif digit == 3:
            S_raw[position] = 1
            S_raw[position + 1] += 1
            S_raw[position + 2] += 1
        else: 
            S_raw[position] = 0
            S_raw[position + 2] += 1
        position += 1
    
    last_two_digits = S_raw[-2:]
    if last_two_digits == [2, 1]:
        S_raw = S_raw[:-2]
    elif last_two_digits == [3, 1]:
        S_raw[-2:] = [1]
    elif last_two_digits == [1, 2]:
        S_raw[-2:] = [1, 0, 1, 1]
    elif last_two_digits == [2, 2]:
        S_raw[-2:] = [0, 1]
    elif last_two_digits == [3, 2]:
        S_raw[-2:] = [1, 1]
    elif last_two_digits == [4, 1]:
        S_raw[-2:] = [0, 0, 1]
    elif last_two_digits == [4, 2]:
        S_raw = S_raw[:-2]
    S = ''.join([str(digit) for digit in S_raw])[::-1]
    print(S)

Solution (Python):
def n_based(n:int, base:int) -> str:
    if n == 0:
        return "0"
    
    ans = ""
    res = n
    
    while abs(res) > 0:
        q = res%base
        if q>=0:
            ans = str(q) + ans
            res //= base
        else:
            q += abs(base)
            ans = str(q) + ans
            res //= base
            res += 1
        
    return ans

N = int(input())
print(n_based(N,-2))

Solution (Python):
N = int(input())

ans = []

if N == 0:
    print('0')
else:
    while abs(N) > 0:
        r = N % -2
        if r != 0:
            N -= 1
            ans.append('1')
        else:
            ans.append('0')

        N //= -2

    print("".join(reversed(ans)))

Solution (Python):
from collections import deque
from sys import stdin, stdout

input = lambda: stdin.readline().rstrip()
write = stdout.write

def main():
    N = int(input())

    ans = '' if N else '0'
    while N:
        if N % 2:
            N -= 1
            ans = '1' + ans
        else:
            ans = '0' + ans
        N //= -2
    write(ans + '\n')

main()

Solution (Python):
N = int(input())
S = ""
while N != 0 :
    if N % (-2) == 0 :
        S = "0"+S
    else :
        S = "1"+S
        N -= 1
    N = N / (-2)
if len(S) != 0 :
    print(S)
else :
    print(0)

Solution (Python):

import sys

n=int(raw_input())
if n==0:
 print 0
 sys.exit()
res=''
while n:
 if n%(-2)==0:
  res+='0'
 else:
  res+='1'
 n+=n%(-2)
 n/=(-2)
print res[::-1]

Solution (Python):
n = int(input())

mb = []
n = -n
while True:
    mb.insert(0,str(n%2))
    n = -n//2
    if n == 0:
        break
ans = ''.join(mb)    
print(ans)

Solution (Python):
a=int(input())
b=''
while a:
 b=str(a&1)+b
 a=-(a//2)
print(b if b else 0)

Solution (Python):
a=int(input())
b=[]
if a==0:
	print(0)
while a:
	b.append(a&1)
	a-=a&1
	a=int(a/-2)
print(''.join(map(str,b[::-1])))

Solution (Python):
a=int(input())
b=[]
if a==0:
	print(0)
while a:
	b.append(a&1)
	a-=a&1
	a=int(a/-2)
print(''.join(map(str,b[::-1])))

Solution (Python):
N = int(input())
S = ""
while N != 0 :
    if N % (-2) == 0 :
        S = "0" + S
    else :
        S = "1" + S
        N -= 1
    N = N / (-2)
if len(S) == 0 :
    print(0)
else :
    print(S)

Solution (Python):
N = int(input())

if N == 0:
    print(0)
    exit()

ans = ""
while abs(N) > 0:
    X = N % -2
    N //= -2
    N += (X < 0)
    ans += str(abs(X))

print(ans[::-1])

Solution (Python):
n = -int(input())
s = ''
while n != 0:
    s += '1' if n & 1 else '0'
    n //= -2
if s == '':
    s = '0'
print(s[::-1])

Solution (Python):
n = int(input())
ans,i = "",0
if n==0: ans = "0"
while n!=0:
	if i%2==0:
		if n%2==0: ans,n = "0"+ans,n//2
		else: ans,n = "1"+ans,(n-1)//2
	else:
		if n%2==0: ans,n = "0"+ans,n//2
		else: ans,n = "1"+ans,(n+1)//2
	i+=1
print(ans)

Solution (Python):
import sys

N = int(input())

if(N == 0):
    print(0)
    sys.exit()

ans = ""
while(N != 0):
    if(N % 2 == 0):
        ans = "0" + ans
    else:
        ans = "1" + ans
    k = N // 2
    N = -1 * k

print(ans)

Solution (Python):
N=int(input())
answer=""

if N==0:
  print(0)
while(N!=0):
  if N%2==1:
    N-=1
    answer="1"+answer
    N=N//-2
  else:
    answer="0"+answer
    N=N//-2
print(answer)

Solution (Python):
import sys

N = int(input())

if(N == 0):
    print(0)
    sys.exit()

ans = ""
while(N != 0):
    mod = N % (-2)
    if(mod != 0):
        ans = "1" + ans
    else:
        ans = "0" + ans
    N = (N + mod) // (-2)
print(ans)

Solution (Python):
n = int(input())

ans = ""
i = 1
while n != 0:
    if n%2 == 1:
        n += (-1)**i
        ans = "1" + ans
    else:
        ans = "0" + ans
    n //= 2
    i += 1

if ans == "":
    ans = "0"
print(ans)

Solution (Python):
import math
N = int(input())
def poss(x, r, result):
    if x == 0:
        return result + '0'
    if x % pow(2, r) != 0:
        x -= pow(-2, r-1)
        result += '1'
    else:
        result += '0'
    return poss(x, r+1, result)

if N == 0:
    print('0')
else:
    r = poss(N, 1, '')[::-1]
    print(r.lstrip('0'))

Solution (Python):
N = int(input())
ans = ""

while N != 0:
    if N % 2 != 0:
        N -= 1
        ans = "1" + ans
    else:
        ans = "0" + ans
    N /= -2
if ans == "":
    ans = "0"

print(ans)

Solution (Python):
N = int(input())
if N == 0:
    print(0)
    exit(0)

S = ""
while N != 0:
    r = N % (-2)
    N = N // (-2)
    if r < 0:
        r += 2
        N += 1
    S += str(r)
print(S[::-1])

Solution (Python):
a=int(input())
b=[]
if a==0:
	print(0)
while a:
	b.append(a&1)
	a-=a&1
	a=int(a/-2)

print(''.join(map(str,b[::-1])))

Solution (Python):
def calc_bit(x):
    i = idx = 0
    if x < 0:
        x = -x
        i = 2
        idx = 1
    else:
        i = 1
        idx = 0
    p = i
    while True:
        if x <= p:
            return idx
        else:
            i *= 4
            p += i
            idx += 2


ans = ""
N = int(input())
pv = -1
f = False
if N == 0:
    ans = "0"
else:
    while True:
        v = calc_bit(N)
        if pv-v > 1 and f:
            ans += "0"*(pv-v-1)
        ans += "1"
        N -= (-2)**v
        if N == 0:
            if v > 0:
                ans += "0"*v
            break
        f = True
        pv = v
print(ans)

Solution (Python):

N=int(input())
def nsin(n):
    if n==0:
        return '0'
    if n==1:
        return '1'  
    return nsin((n-1)/(-2))+'1' if n%2 else nsin(n/(-2))+'0'

print(nsin(N))

Solution (Python):


N = int(input())

ans = ""
while N != 0:
    
    if N % 2 == 0:
        ans = "0" + ans
    else:
        
        N -= 1
        ans = "1" + ans
    
    N /= -2

if ans == "":
    ans = 0

print(ans)

Solution (Python):
N = int(input())

if N == 0:
    print(0)
else:
    ans = ''
    while N != 0:
        if N % 2:
            N -= 1
            ans += '1'
        else:
            ans += '0'
        N = N // -2
    print(ans[::-1])

Solution (Python):
def solve(n):
    if n == 0:
        return '0'

    ans = ''
    p = 0
    d = 0
    while n + p:
        if (n & 1) ^ p:
            ans += '1'
            if d ^ p:
                p ^= 1
        else:
            ans += '0'
        n >>= 1
        d ^= 1

    return ans[::-1]


n = int(input())
print(solve(n))

Solution (Python):
N = int(input())
ans = ""
if N == 0:
    ans = "0"
while N != 0:
    if N % 2 != 0:
        N -= 1
        ans = "1" + ans
    else:
        ans = "0" + ans

    N //= -2

print(int(ans))

Solution (Python):
n = int(input())

if n == 0:
    print('0')
else:
    ans = ''
    while n != 0:
        if n % (-2) == 0:
            ans = '0' + ans
        else:
            ans = '1' + ans
            n -= 1
        n /= -2
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
N=int(input())
def f(x):
    if x==0:
        return "0"
    if x%2==1:
        return f((1-x)//2)+"1"
    else:
        return f((-x)//2)+'0'
if N==0:
    print('0')
    sys.exit()
print(f(N)[1:])

Solution (Python):
import sys

N = int(input())

if(N == 0):
    print(0)
    sys.exit()
elif(N < 0):
    mask = 1
    N = -1 * N
else:
    mask = 0
S = bin(N)[2:]

ans = ""

i = 0
up1 = 0
up2 = 0
for c in (reversed(S)):
    if((i + mask) % 2 == 0):
        if(up1 == 1):
            if(c == "0"):
                up1 = 0
                up2 = 0
                ans = "1" + ans
            else:
                up1 = 1
                up2 = 1
                ans = "0" + ans
        else:
            up2 = 0
            up1 = 0
            ans = c + ans
    else:
        if(up2 == 0):
            up1 = int(c)
            up2 = 0
            ans = c + ans
        else:
            up1 = up2
            up2 = 0
            if(c == "0"):
                ans = "1" + ans
            else:
                ans = "0" + ans

    
    i += 1


if(up2 == 1):
    ans = str(up2) + str(up1) + ans
elif(up1 == 1):
    ans = str(up1) + ans
print(ans)

Solution (Python):
N = int(input())
def n_ary_notation(N, n):
  if N == 0:
    return '0'
  else:
    s = ''
    while N:
      s = str(N % abs(n)) + s
      N -= N % abs(n)
      N //= n
    return s
print(n_ary_notation(N, -2))

Solution (Python):
N = int(input())
def n_ary_notation(N, n):
  if N == 0:
    return '0'
  else:
    s = ''
    while N:
      s = str(N % abs(n)) + s
      N -= N % abs(n)
      N //= n
    return s
print(n_ary_notation(N, -2))

Solution (Python):
n=int(input())
s=''
while n!=0:
  s=str(n%2)+s
  n=-(n//2)
print(s*(s!='')or 0)

Solution (Python):


n = int(input())
answer = ""

def kenzan(ans):
    val = 0
    ans.reverse()
    for i in range(len(ans)):
        val += answer[i]*(-2)**i
    return int(val)

i = 1

while(n != 0):
    if n % 2 == 0:
        answer = "0" + answer
    else:
        answer = "1" + answer
        n -= 1
    n /= -2
if answer == "":
    answer = 0
print(answer)

Solution (Python):
N = int(input())
ans = ''
if N == 0:
    print(0)
    exit(0)
else:
    while N != 0:
        r = N % -2
        if r != 0:
            ans += "1"
            N -= 1
        else:
            ans += "0"
        N //= -2
    print(ans[::-1])

Solution (Python):
n=int(input())
s=''
while n!=0:
  s=str(n%2)+s
  n=-(n//2)
print(s*(s!='')or 0)

Solution (Python):


n = int(input())
m=n
answer = []

def kenzan(ans):
    val = 0
    ans.reverse()
    for i in range(len(ans)):
        val += answer[i]*(-2)**i
    return int(val)

i = 1
while(n != 0):
    
    if n % (2**i) == 0:
        answer.append(0)
    else:
        answer.append(1)
        n = n-((-2)**(i-1))
    i += 1
answer.reverse()
if answer == []:
    answer.append(0)
print("".join(str(i) for i in answer))

Solution (Python):



n = int(input())

ans = ''
while(n != 0):
    if n % 2 != 0:
        n -= 1
        ans = '1' + ans
    else:
        ans = '0' + ans

    n /= -2

if ans == '': ans = '0'

print(ans)

Solution (Python):
n = int(input())
if n == 0:
    ans = '0'
else:
    ans = ''
    while n != 0:
        if n % 2 == 1:
            ans = '1' + ans
            n -= 1
        else:
            ans = '0' + ans
        n //= -2
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
N=int(input())
def f(x):
    if x==0:
        return "0"
    if x%2==1:
        return f((1-x)//2)+"1"
    else:
        return f((-x)//2)+'0'
if N==0:
    print('0')
    sys.exit()
print(f(N)[1:])

Solution (Python):


def main():
    n = int(input())

    ans = []

    if n == 0:
        print(0)
        exit()
    
    while True:
        if n % (-2) == -1:
            ans.append(1)
            n = (n // -2) + 1
        elif n % -2 == 0:
            ans.append(0)
            n //= -2
        if n == 1:
            ans.append(1)
            break
    ans.reverse()
    print(''.join(list(map(str, ans))))

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
if n == 0:
	print '0'
	quit()
ans = ''
while n :
	
	if n%(-2) == 0 :
		ans += '0'
	else :
		ans += '1'
	n += (n%(-2))
	n/= (-2)

print ans[::-1]

Solution (Python):
N=input()

if N==0: print 0;quit()
ans=""
while N!=0:
	if N%(-2)!=0:
		ans+="1"
		N-=1
	else:
		ans+="0"
	N/=(-2)

print ans[::-1]

Solution (Python):
N = float(input())

if N==0:
  print(0)
else:
  q = N
  r_s = []

  while q!=1:
    hoge = (q-1) / (-2)
    if hoge.is_integer():
      r = int(1)
      q = float(hoge)
    else:
      r = int(0)
      q = float(q/(-2))
  
    r_s.append(r)
  r_s.append(1)
  r_s = r_s[::-1]

  for i in range(len(r_s)):
    print(r_s[i], end="")

Solution (Python):
N = int(input())
n = 0
k = 0
even = True
if N > 0:
    while N > 0:
        if N & 1:
            if even:
                if n & 1 << k:
                    n = n + (5<<k)
                else:
                    n = n + (1<<k)
            else:
                if n & 1 << k:
                    n = n - (1<<k)
                else:
                    n = n + (3<<k)
        even = not even
        N = N >> 1
        k += 1
else:
    N = -N
    while N > 0:
        if N & 1 != 0:
            if even:
                if n & 1 << k:
                    n = n - (1<<k)
                else:
                    n = n + (3<<k)
            else:
                if n & 1 << k:
                    n = n + (5<<k)
                else:
                    n = n + (1<<k)
        even = not even
        N = N >> 1
        k += 1
print(bin(n)[2:])

Solution (Python):
N=int(input())

lr = ""
i=1

if N==0:
    print(0)

else:    
    while N!=0:
        if N%(2**i)!=0:
            lr = "1" + lr
            N = N - (-2)**(i-1)
        else:
            lr = "0" + lr

        i+=1

    print(lr)

Solution (Python):
n = int(input())
if n == 0:
    ans = "0"
else:
    ans = ""
while n != 0:
    if n % 2 == 0:
        ans = "0" + ans
    else:
        ans = "1" + ans
    n = -(n // 2)

print(ans)

Solution (Python):
import sys
N = int(input())
if N == -1:
  print('11')
  sys.exit()
if N == 0:
  print('0')
  sys.exit()
if N == 1:
  print('1')
  sys.exit()

def num(N):
  mi = 0
  ma = 1
  k = 1
  while mi > N or ma < N:
    mi = min(mi,mi+(-2)**k)
    ma = max(ma,ma+(-2)**k)
    k += 1
  return k-1
rem = 0
ansli = []
def ans(N):
  while abs(N)>0:
    ansli.append(num(N))
    N = N-(-2)**num(N)
  return ansli

ans(N)
answer = ''
m = max(ansli)
while m >= 0:
  if m in ansli:
    answer += '1'
  else:
    answer += '0'
  m += -1
  
print(answer)

Solution (Python):
n = int(input())

def solve(n):
    if n == 0:
        print(0)
        return
    ans = ''
    while n != 0:
        if n%2 == 1:
            ans = '1'+ans
            n = int((n-1)/(-2))
        else:
            ans  = '0'+ans
            n = int(n/(-2))
    print(ans)
    return
        
solve(n)

Solution (Python):
N, = map(int, raw_input().split())
i=0
s=""
while N!=0:
  m = 1 if (N%(1<<(i+1))>0) else 0
  s = str(m)+s
  N-= m * ((-2)**i)
  i += 1
print 0 if s=="" else s

Solution (Python):
N = int(input())

def solve(N):
    result = ""
    k = 1
    while 1:
        c = N % 2
        result = "01"[c] + result
        N = (N - k * c) // 2
        k = -k
        if N == 0:
            break
    return result

print(solve(N))

Solution (Python):
n,ans = int(input()),[]
while n:
	ans.append(str(abs(n)%2))
	n = (n-abs(n)%2)//(-2)
print("".join(reversed(ans)) if ans else "0")

Solution (Python):
n = int(input())
if n == 0:
    ans = '0'
else:
    ans = ''
    while n != 0:
        ans = str(n % 2) + ans        
        n -= 1
        n *= (-1)
        n //= 2
print(ans)

Solution (Python):
N = int(input())

A,S = [0]*32,[0]*32
A[0],A[1],S[0],S[1] = 1,-2,1,-2
for i in range(2,32):
    A[i] = A[i-1]*(-2)
    S[i] = S[i-2] + A[i]

X = ["0"]*32
t = 0
flg = True
while N != 0:
    if N > 0:
        for i in range(32):
            if S[i] >= N:
                break
    else:
        for i in range(32):
            if S[i] <= N:
                break
    X[i] = "1"
    N -= A[i]

print(int("".join(X)[::-1]))

Solution (Python):
N = int(input())

if N == 0:
    ans = 0
else:
    ans = ''
    while N != 0:
        if N % 2 == 0:
            ans = '0' + ans
        else:
            ans = '1' + ans
            N -= 1
        N //= -2
print(ans)

Solution (Python):

import math,string,itertools,fractions,heapq,collections,re,array,bisect

def n():
    return int(input())

N = n()
ans = ''
if N == 0:
    print(0)
    exit()

while N != 0:
    if abs(N%2) == 1:
        ans = '1' + ans
        N -= 1
    else:
        ans = '0' + ans
    N = N//(-2)

print(ans)

Solution (Python):
N = int(input())

ans = 0
if N != 0:
    s = ''
    while N != 0:
        if N % 2 != 0:
            N -= 1
            s = '1' + s
        else:
            s = '0' + s
        N //= -2
    ans = s

print(ans)

Solution (Python):
N = int(input())



if N == 0:
    print(0)
elif N > 0:
    co = [0 for i in range(31)]

    a = 2
    i = 1

    co[0] = N % 2
    while a <= N:
        co[i] = ((N - a) // (2 ** i) + 1) % 2


        i = i + 1
        if i % 2 == 1:
            if i == 1:
                pass
            else:
                a = a + 2 ** (i - 1)

    ans = 0
    for i in range(31):
        ans = ans + (10 ** i) * co[i]
    print(ans)
else:
    co = [0 for i in range(32)]
    N = - N

    a = 1
    i = 1
    co[0] = N % 2
    while a <= N:
        co[i] = ((N - a) // (2 ** i) + 1) % 2


        i = i + 1
        if i % 2 == 0:
            a = a + 2 ** (i - 1)

    ans = 0
    for i in range(32):
        ans = ans + (10 ** i) * co[i]
    print(ans)

Solution (Python):
N=-int(input())
if N==0:
    print(0)
else:
    tmp=[]
    while N!=0:
        tmp.insert(0,N%(2))
        N=-N//2
    s=''.join([str(_) for _ in tmp])
    print(s)

Solution (Python):

N = int(input())

S = ''
if N == 0:
    S = '0'

i=0
while abs(N) > 0:
    if (N % 2 ** (i+1)) == 0:
        S = '0' + S
    else:
        S = '1' + S
        N -= (-2) ** i
    i+=1
print(S)

Solution (Python):
N = int(input())

def solve(N):
    if N == 0:
        return "0"
    result = ""
    n = N
    i = 0
    while n:
        k = (-2)**i
        if n & (1 << i):
            n -= k
            result = "1" + result
        else:
            result = "0" + result
        i += 1
    return result

print(solve(N))

Solution (Python):
def mm(n):
	global S
	if n==0:
		S=0
	elif n%2==0:
		mm(n/(-2))
		S=S*10
	elif n==1:
		S=1
	elif n%2==1:
		mm((n-1)/(-2))
		S=S*10+1

import sys
sys.setrecursionlimit(10000)
N=int(input())
mm(N)
print(S)

Solution (Python):
import sys
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()

N = ni()

if N==0:
  print(0)

s=''
while N:
  if N%2:
    s = '1' + s
    N -= 1
  else:
    s = '0' + s
  N /= -2

print(s)

Solution (Python):
n = int(input())
ans = str()
if n == 0:
  ans = 0
i = 0
while n != 0:
  b = n%2
  if (b==1 or b== -1):
    ans = "1" + ans
  else:
    ans = "0" + ans
  n -= abs(b) *(-1) ** (i)
  n = n//2
  i += 1
print(ans)

Solution (Python):
N = int(input())

res = ''
while N != 0:
    if N % 2 == 0:
        res += '0'
    else:
        res += '1'
        N -= 1
    N //= -2

if len(res) == 0:
    res = '0'
print(res[::-1])

Solution (Python):
n = int(input())

ans = ''
i = 0
if(n == 0):
    print(0)
    exit()
while(abs(n) > 1):
    if(n % 2 ** (i+1) == 0): ans += '0'
    else:
        ans += '1'
        n -= (-2) ** i
    i += 1

print(ans[::-1])

Solution (Python):
N=int(input())
res=""
while N!=0:
	if N%2==0:
		res+="0"
	else:
		N-=1
		res+="1"
	
	N//=-2
if len(res)==0:
	res="0"
print(res[::-1])

Solution (Python):

N = int(input())

data = N
if data == 0:
    re = '0'
else:
    re = ''

    while True:
        if data % 2 == 1:
            data -= 1 
            re = '1' + re
        else:
            if data // -2 != 0:
                re = '0' + re
            else:
                break
        data = data // -2
    
print(re)

Solution (Python):
n = int(input())
tmp = int("1010101010101010101010101010101010", 2)
print(format(tmp ^ (tmp + n), 'b'))

Solution (Python):
def solve(N):
    if N == 0:
        return '0'
    if N == 1:
        return '1'

    if N % 2 == 0:
        return '0'+solve(N//-2)
    if N % 2 ==1:
        return '1'+solve((N-1)//-2)

print(solve(int(input()))[::-1])

Solution (Python):
N = int(input())

if N<0:
  negative = True
elif N==0:
  print(0)
  exit()
else:
  negative = False

N = abs(N)

a = bin(N)
a = a[2:]
a = [int(i) for i in a]
a.reverse()
a.extend([0,0,0,0,0,0])

for i,num in enumerate(a[-2::-1]):
  digit = len(a)-2-i
  if digit % 2:
    a[digit+1] += num

if negative:
  for i,num in enumerate(a[-2::-1]):
    digit = len(a)-2-i
    a[digit+1] += num


for i,num in enumerate(a):
  while a[i]>1:
    a[i] -= 2
    if a[i+1]:
      a[i+1] -= 1
    else:
      a[i+1] += 1
      a[i+2] += 1

flag = 0
for i in a[::-1]:
  if i == 1:
    flag = i
  if flag:
    print(i,end='')

Solution (Python):
N = int(input())
s = ""
while True:
    p = N // (-2)
    q = N % (-2)
    if N < 0 and q != 0:
        p += 1
        q = 1
    if N > 0 and q != 0:
        p += 1
        q = 1

    s += str(q)
    if p == 0:
        break

    N = p

print(s[::-1])

Solution (Python):
a=int(input())
sum=0
s=''

if a!=0:
    while(a!=1):
        if a%(-2)==-1:
            s=s+'1'
            a=a-1
            a=a/-2
        else:
            s = s + '0'
            a=a/-2
    s=s+'1'
    for i in range(len(s)):
        print(s[len(s)-1-i],end='')
    print()
else:
    print(0)

Solution (Python):
num = int(input())

def to_negative_base(n, neg_base):
    if n == 0:
        return 0

    converted = ""
    while n != 0:
        
        remainder = n - neg_base * (n // neg_base)
        
        n = n // neg_base

        if remainder < 0:
            remainder += (-neg_base)
            n += 1

        converted = str(remainder) + str(converted)

    return converted

print(to_negative_base(num, -2))

Solution (Python):
import math

n = int(input())
s = str(bin(n))[2:]
p = 0
if n >= 0:
    while 1:
        s = str(bin(n))[2:]
        ls = len(s)
        lsp = ls - p - 1
        if ls <= p:
            break
        if p % 2 == 0:
            p += 1
            continue
        if s[lsp] == '0':
            p += 1
            continue
        p += 1
        n += 2**p
else:
    n = abs(n)
    while 1:
        s = str(bin(n))[2:]
        ls = len(s)
        lsp = ls - p - 1
        if ls <= p:
            break
        if p % 2 == 1:
            p += 1
            continue
        if s[lsp] == '0':
            p += 1
            continue
        p += 1
        n += 2**p
print(str(bin(n))[2:])

Solution (Python):
memo=-1
n = int(input())
if n==0: 
    print("0")
    exit()
while n != 0:
    if n>0:
        i=1
        j=0
        while i<n:
            i|=i<<2
            j+=2
        n-=1<<j;
    else:
        i=2
        j=1
        while i<abs(n):
            i|=i<<2
            j+=2
        n+=1<<j;
    if memo != -1:
        for i in range(memo-j-1):
            print("0",end="")
    print("1",end="")
    memo=j
for i in range(memo):
    print("0",end="")
print("")

Solution (Python):
N = int(input())
if N >= 0:
  if N == 0:
    print(0)
  elif N == 1:
    print(1)
  else:
    s = 2
    j = 2
    i = 1
    while s + j**2 <= N:
      i += 1
      s += j**2
      j*= 2
  
    k = 2 * i + 1
    a  = bin(int('10'*i, 2)^(N-s))[2:]
    if len(a) < k-1:
      a = '0'*(k-1-len(a)) + a
    print('1' + a)
else:
  s = -1
  j = -2
  i = 1
  while N <= s + j:
    s += j
    j *= 4
    i += 1
  k = 2 * i
  print(bin(int('10'*i, 2)^(N-(s+j)-1))[2:])

Solution (Python):
a=int(input())
sum=0
s=''
'''if a<0:
    b = abs(a)
    if b%2==1:
        b=b+1
        print(str(bin(b))[2:-1]+'1')
    else:
        print(str(bin(b))[2:-1])'''
if a!=0:
    while(a!=1):
        if a%(-2)==-1:
            s=s+'1'
            a=a-1
            a=a/-2
        else:
            s = s + '0'
            a=a/-2
    s=s+'1'
    for i in range(len(s)):
        print(s[len(s)-1-i],end='')
    print()
else:
    print(0)

Solution (Python):

from bisect import bisect_left
def inpl(): return list(map(int, input().split()))

N = int(input())
A = []
B = []
for i in range(2**16):
    A.append(int(("0{}"*16).format(*list(bin(i)[2:].zfill(16))), 2))
for i in range(2**16):
    B.append(-int(("{}0"*16).format(*list(bin(i)[2:].zfill(16))), 2))

for j, b in enumerate(B):
    i = bisect_left(A, N-b)
    if i == len(A):
        continue
    a = A[i]
    if a+b == N:
        ans = [""]*32
        ans[::2] = list(bin(j)[2:].zfill(16))
        ans[1::2] = list(bin(i)[2:].zfill(16))
        print(int("".join(ans)))
        break

Solution (Python):


import bisect
n=int(input())

if n == 0:
    print(0)
else:
    p = [1]
    m = []
    ps = 5
    ms = 2
    w = 4
    while w<abs(n)*4:
        p.append(ps)
        m.append(ms)
        w = w *4
        ps += w
        ms += w//2
    
    
    ass =[]
    
    while n != 0:
        if n > 0:
            jkl = bisect.bisect_left(p,n)
            ass.append(jkl*2)
            n -=4**jkl
        if n < 0:
            n = (-1)*n
            jkl = bisect.bisect_left(m,n)
            ass.append(jkl*2+1)
            n = n*(-1)
            n += (4**jkl)*2
    ans = 0
    for i in range(len(ass)):
        ans += 10**ass[i]
    print(ans)

Solution (Python):
N = int(input())

bin=[]
p = ['00','10','01','11']
m = ['00','11','01','10']
ans=[]
if N < 0:
    N = -1*N
    minus = True
else:
    minus = False
if N == 0:
    print(0)
else:
    while(N != 0):
        n = N % 4
        N = N // 4
        if minus:
            ans.append(m[n])
            if n == 3: N += 1
        else:
            ans.append(p[n])
            if n == 2 or n == 3: N += 1
    bin.append(n)
    ans ="".join(ans)
    ans = ans[::-1]
    print(ans[ans.find('1'):])