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):

import sys
import math
import os
import itertools

class cin():
    def int():
        return int(sys.stdin.readline().rstrip())
    def string():
        return sys.stdin.readline().rstrip()
    def mapInt():
        return [int(x) for x in cin.string().split()]
    def stringList(n):
        return [input() for i in range(n)]
    def intListList(n):
        return [cin.mapInt() for i in range(n)]

class Util():
    def roundUp(a,b):
        return -(-a // b)
    def toUpperMultiple(a,x):
        return Util.round_up(a,x) * x
    def toLowerMultiple(a,x):
        return (a // x) * x

N = cin.int()

ans = ""
while(N != 0):
    q = N % 2
    p = (N - q) // (-2)
    ans += str(q)
    N = p
if ans == "":
    ans += "0"
print(ans[::-1])

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

ans = ''

if n == 0:
    print('0')

while n != 0:
    r = n % 2 

    if r < 0:
        r = r + 2
    
    n = (n-r) / (-2)

    ans = ans + str(int(r))

ans = list(ans)    
ans.reverse()
print(''.join(ans))

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

ans = 0
base = 1
n = -n
while (n != 0):
   p = abs(n % (-2))
   n = (n + p) // (-2)
   ans += p * base
   base *= 10

print(ans)

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

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

if n == 0:
    print(0)
    exit()
t = []
while n != 0:
    s = n%-2
    if s == 0:
        t.append(0)
    else:
        t.append(1)
    n //= -2

t = t[::-1]
for i in t:
    print(i, end='')

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

Solution (Python):

N=int(input())
if N==0:
  print(0)
  exit(0)
d=-2
ans=[]
while N!=0:
    r=N%(d)
    if r<0:
        r+=2
    N=(N-r)//(d)
    ans.append(str(r))
    
print("".join(ans[::-1]))

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

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

def dec_to_n(N, n):
    if N == 0:
        return "0"
    digits = []
    base = 1
    while N != 0:
        if N % (base * n) == 0:
            digits.append('0')
        else:
            digits.append('1')
            N -= base
        base *= n
    return "".join(digits[::-1])

print(dec_to_n(N, -2))

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())

def dec_to_n(N, n):
    if N == 0:
        return "0"
    digits = []
    i = 0
    base = 1
    while N != 0:
        if N % (base * n) == 0:
            digits.append('0')
        else:
            digits.append('1')
            N -= base
        i += 1
        base *= n
    return "".join(digits[::-1])

print(dec_to_n(N, -2))

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
i = 0
ans = []
if N == 0:
    print(0)
    sys.exit()
while N != 0:
    i += 1
    if N % 2 == 0:
        N //= 2
        ans.append("0")
    else:
        if i % 2 == 1:
            N -= 1
            N //= 2
            ans.append("1")
        else:
            N += 1
            N //= 2
            ans.append("1")
print("".join(ans[::-1]))

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

while n != 0:
    r = n % 2
    if r < 0:
        r += 2
    n = int((n - r) / (-2))
    st += str(r)

st = st[::-1]

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

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

def main():
    n = int(input().strip())
    if n == 0:
        print(0)
        return
    ans = ''
    c = 0
    while n != 1:
        c += 1
        s, a = divmod(n, -2)
        
        if a == -1:
            s += 1
            a = 1
        ans += str(a)
        n = s
    ans += '1'
    print(''.join(reversed(ans)))

if __name__ == '__main__':
    main()

Solution (Python):
from math import log2

def main():
    N = int(input())
    if N == 0:
        print(0)
        return
    Ans = []
    while N !=  0:
        r = N%2
        Ans.append(r)
        N = -1*( N // 2)
    print(*Ans[::-1],sep="")
    return

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
a = []
if N == 0:
  a.append("0")
while N != 0:
  a.append(str(N % 2))
  N = -(N // 2)
print("".join(reversed(a)))

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

if n != 0:
	ans = []
	while n != 0:
		ans.append(abs(n % -2))

		n += n % -2
		n /= -2
		n = int(n)

	print(''.join([str(i) for i in reversed(ans)]))
else:
	print(0)

Solution (Python):
N=int(input())
A=[]
if N==0:
  print(0)
else:
  while(abs(N)!=0):
    a=N%2
    A.append(a)
    N=(N-a)//(-2)
B=A[::-1]
print(*B,sep='')

Solution (Python):
import math
N = int(input())
if N == 0:
    print(0)
    exit()
ans = ""
while N != 1:
    if N % 2 == 0:
        N //= (-2)
        ans = "0" + ans
    else:
        if N > 0:
            N //= (-2)
            N += 1
            ans = "1" + ans
        else:
            N //= (-2)
            N += 1
            ans = "1" + ans
ans = "1" + ans    
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()

  if n==0:
    return 0

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

  return ans


print(main())

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

i = 0
base = 1
digits = ''

while n!= 0:
  if n % (base*2) == 0:
    digits += '0'
  else:
    digits += '1'
    n -= base 
  
  i += 1
  base *= -2

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

Solution (Python):
N = int(input())
tmp = []
if(N == 0):
  print('0')
else:
  while(abs(N)!=0):
    tmp.append(N%2)
    N = (N - N % 2) // -2
tmp.reverse()
print(''.join([str(n) for n in tmp]))

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    if N == 0:
        print(0)
        exit()

    ans = [0] * 100

    ruiseki = [1, -2]
    for i in range(2, 100):
        if i & 1:
            ruiseki.append(-2 ** i + ruiseki[i - 2])
        else:
            ruiseki.append(2 ** i + ruiseki[i - 2])

    while N != 0:
        for i in range(100):
            if N < 0 and i & 1 and ruiseki[i] <= N:
                N -= -2 ** i
                ans[i] = 1
                break
            elif N > 0 and not i & 1 and ruiseki[i] >= N:
                N -= 2 ** i
                ans[i] = 1
                break


    ans2 = []
    for i in range(99, -1, -1):
         if ans[i] == 1 or len(ans2) > 0:
             ans2.append(ans[i])

    print("".join(map(str, ans2)))

if __name__ == '__main__':
    main()

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

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

ans=""
for i in range(1000):
    ans+=str(n%2)
    n//=-2
    if n==0:
        break
print(ans[::-1])

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

Solution (Python):

N = int(input())

ans = ''

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

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

Solution (Python):

N = int(input())

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

ans = ""

while N != 0:
  bit = N % -2
  if (bit < 0):
    bit += 2
  ans = str(bit) + ans
  N = (N - bit) // (-2)

print(ans)

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

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

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=="":
  print("0")
else:
  print(ans)

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

mbits = []

while abs(n) > 0:
    mbits.append(n % 2)
    n = n // 2 * (-1)

if len(mbits) == 0:
    mbits = [0]

ans = map(str, reversed(mbits))
ans = ''.join(ans)
print(ans)

Solution (Python):
N = int(input())
ans = []
if N == 0:
  ans.append("0")
while N != 0:
  ans.append(str(N % 2))
  N = -(N // 2)
ans.reverse()
print("".join(ans))

Solution (Python):
import sys
bbn=1000000007
	



def mkm2(a_ll):
	ccc=0
	for i, c in enumerate(a_ll):
		ccc += ((-2)**i)*(c==1)
	return ccc

def show(a_ll):
	ret = ''.join([str(i) for i in a_ll[::-1]])
	return ret


def main():
	a = int(input())
	if a == 0:
		return 0
	a=-a
	
	ret=[]
	while mkm2(ret) < a and False:
		ret.append(0)
		ret.append(1)
		pa(mkm2(ret))
		pa(ret)
	
	while a != 0:
		if a %(-2)==0:
			ret.append(0)
		else:
			ret.append(1)
		a = a // (-2)
		
	pa(mkm2(ret))
	print(show(ret))
	
	

isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		
			
	ret = main()
	if ret is not None:
		print(ret)

Solution (Python):
import sys

n = int(sys.stdin.readline().rstrip())

def base_convert(n, b):
    res = ''
    while n:
        r = abs(n % b)
        res = str(r) + res
        n = (n - r) // b

    return int(res) if res else 0

def main():
    return base_convert(n, -2)

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys

n = int(sys.stdin.readline().rstrip())

def base_convert(n, base):
    res = []
    b = abs(base)
    while n:
        q, r = divmod(n, b)
        res.append(r)
        n = b * q // base
    try:
        return int(''.join(list(map(str, res)))[::-1])
    except:
        return 0

def main():
    return base_convert(n, -2)

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys

n = int(sys.stdin.readline().rstrip())

def to_neg_base(n, neg_base):
    if neg_base > -2:
        sys.exit('base must be at most -2')
    b = abs(neg_base)
    res = [0] * 100
    if n >= 0:
        res[0] = n
        i = 0
    else:
        q, r = divmod(n, b)
        res[0] = r; res[1] = abs(q)
        i = 1

    while res[i] >= b:
        q, r = divmod(res[i], b)
        m = min(q, res[i+1])
        q -= m
        res[i+1] -= m
        res[i] = r
        res[i+1] += (b - 1) * q
        res[i+2] += q
        i += 1

    res = ''.join(list(map(str, res)))[::-1]
    try: 
        return int(res[res.index('1'):])
    except:
        return 0

def main():
    return to_neg_base(n, -2)

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
n=int(input())
if n==0:
    print(0)
else:
    a=abs(n)
    if n>0:
        p=0
    else:
        p=1
    inf=2**p
    while True:
        if a<=inf:
            break
        else:
            p+=2
            inf+=2**p
    sp=p
    while p>=0:
        if p==sp:
            if p%2==0:
                
                n-=2**p
                
            else:
                
                n+=2**p
                
            p-=1
            ans="1"
        elif p%2==0 and 2*abs(n)>=abs(n-2**p):
            
            n=n-2**p
            
            p-=1
            ans=ans+"1"
        elif p%2==1 and 2*abs(n)>=abs(n+2**p):
            
            n=n+2**p
            
            p-=1
            ans=ans+"1"
        else:
            
            p-=1
            ans=ans+"0"
    if len(ans)<sp+1:
        ans+="0"*(sp+1-len(ans))
    print(ans)

Solution (Python):
N = int(input())
a = []
if N == 0:
  a = ["0"]
while N != 0:
  a.append(str(N % 2))
  N = -(N // 2)
  
print("".join(list(reversed(a))))

Solution (Python):
def main():
    N = int(input())
    S = ""
    base = 2
    while N:
        S = str(N % base) + S
        N -= N % base
        N //= -base
    print(S if S else "0")
    return


main()

Solution (Python):
def main():
    N = int(input())
    S = ""
    base = 2
    while N:
        S = str(N % base) + S
        if N % base:
            N -= N % base
        N //= -base
    print(S if S else "0")
    return


main()

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


main()

Solution (Python):
import sys

n = int(input())

if n == 0:
    print("0")
    sys.exit(0)

sum = 0
ans = ""

count = 0
d = 1

while n != sum:
    mod = (n - sum) % (d * 2)
    

    if mod != 0:
        ans = "1" + ans
        sum += d * (1 if count % 2 == 0 else -1)
    else:
        ans = "0" + ans

    count += 1
    d *= 2

print(ans)

Solution (Python):





N = int(input())

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

ans = ''
while N != 0:
    if N & 1:  
        ans += '1'
        N /= -2  
        N = int(N + 0.5)

    else:
        ans += '0'
        N //= -2


print(ans[::-1])

Solution (Python):





N = int(input())

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

ans = ''
while N != 0:
    if N & 1:  
        ans += '1'
        N /= -2
        if N > 0:
            N += 1
        N = int(N)
    else:
        ans += '0'
        N //= -2


print(ans[::-1])

Solution (Python):
from _collections import deque


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
import scipy
from collections import deque
from math import sqrt
from math import floor


"""
need to consider the case that ticket is not enough to lower everything
"""

N = gi()

ans = []

while (N != 0):  
    r = N % 4
    
    if (r == 0):  
        ans.append(0)
        ans.append(0)  
    elif r == 1:
        ans.append(1)
        ans.append(0)
    elif r == 2:
        ans.append(0)
        ans.append(1)
        N += 4
    else:
        ans.append(1)
        ans.append(1)
        N += 4
    N //= 4  

if len(ans):
    ans.reverse()
    si = 0
    if (ans[si] == 0):  
        si += 1

    for i in range(si, len(ans)):
        print(ans[i], end="")
else:
    print(0)

Solution (Python):
N = int(input())
NN = N
b = ''
i = 0
if N == 0:
  b = '0'
else:
  while (NN!=0):
    bi = abs(NN)%2
    b=str(bi)+b
    NN = (NN-bi*(-1)**i)//2
    i+=1
print(b)

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

Solution (Python):
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


N = int(sys.stdin.buffer.readline())

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

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

Solution (Python):
import math
N = int(input())
tmp = N
ans = []

for i in range(len(bin(N))):
    
    
    k = tmp % -2**(i+1)
    
    if k == - 2**i:
        ans.append(1)
        tmp -= (-2)**i
    else:
        ans.append(0)

tmp = 0
id = len(ans)
for i in range(len(ans)):
    if ans[i]:
        tmp += (-2)**i
    
    if tmp == N:
        id = i+1
        break


ans = ans[:id]

print("".join(map(str, ans[::-1])))

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
















i=0
S=''
while N:
    s=N&1
    S=str(s)+S
    if i:
        N=N//2+(s*N//N)
    else:
        N=N//2
    i^=1
print(S if S else 0)

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

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

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


reverse_ans = []
i = 0
base = -2

while n != 0:
    if n % (base**(i+1)) == 0:
        reverse_ans.append(0)
    else:
        reverse_ans.append(1)
        n -= base**i

    i += 1

ans = reverse_ans[::-1]
print(*ans, sep ='')

Solution (Python):
def f(n):
    if n==0:
        x[-1]="0"
        return
    if n==1:
        x[-1]="1"
        return
    if n>0:
        k = 0
        while True:
            if 2**k>=n:
                break
            k += 2
        if n<=(2**k-1)//3:
            k -= 2
        x[K-k]= "1"
        f(n-2**k)
    else:
        k = 1
        while True:
            if (-2)**k<=n:
                break
            k += 2
        if n>=((-2)**k+2)//3:
            k -= 2
        x[K-k] = "1" 
        f(n-(-2)**k)
K = 31
x = ["0" for _ in range(K+1)]      
N = int(input())
f(N)
for i in range(K+1):
    if x[i]=="1":
        ind = i
        break
if N!=0:
    print("".join(x[ind:]))
else:
    print(N)

Solution (Python):
N = int(input())
total = 0
i = 0
idx_list = []

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

if N < 0:
  while total > N:
    total += (-2) ** (2 * i + 1)
    idx_list.append(2 * i + 1)
    i += 1
  diff = abs(total - N)
  flip_str = str(bin(diff))[2:]
else:
  while total < N:
    total += (-2) ** (2 * i)
    idx_list.append(2 * i)
    i += 1
  diff = abs(total - N)
  flip_str = str(bin(diff))[2:]

i = 0
ans = ''
while i <= max(idx_list):
  if i in idx_list:
    ans = '1' + ans
  else:
    ans = '0' + ans
  i += 1

print(bin(int(ans, 2) ^ int(flip_str.zfill(len(ans)), 2))[2:])

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

ans = ""

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

Solution (Python):
from math import ceil
n = int(input())

lst = []
if n == 0:
    ans = 0
else:
    while n!= 1:
        lst.append(n-(-2)*ceil(n/(-2)))
        n = ceil(n/(-2))
    else:
        lst.append(1)
    lst = [str(c) for c in reversed(lst)]
    ans = "".join(lst)

print(ans)

Solution (Python):
import math

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

bits = []
for keta in range(5 + int(math.log2(abs(N)))):
    if N % 2 == 1:
        bits.append("1")
        N -= 1
    else:
        bits.append("0")
    N //= -2
    if N == 0:
        break

print("".join(bits[::-1]))

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

Solution (Python):
n = input()
negBase = -2

if (n == 0): 
    converted = "0"

else:
    converted = "01"
    while (n != 0):           
        remainder = n % (negBase) 
        n = int(n/negBase) 
  
        if (remainder < 0): 
            remainder += ((-1) * negBase) 
            n += 1
  
        converted = str(remainder) + converted 
          
    converted = converted[0:len(converted)-2]

print(converted)

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

temp = N
S = ""
while temp != 0:
    rem = temp % -2
    div = temp // -2
    if rem == -1:
        div += 1
        rem = 1
    temp = div
    S = str(rem) + S
if N == 0:
    print(0)
else:
    print(S)

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

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

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()

ans = []
if n == 0:
    print(0)
    quit()
while 1:
    if n == 0:
        break
    if n % 2:
        ans.append(1)
        n -= 1
    else:
        ans.append(0)
    n //= -2
print(''.join(list(map(str,ans[::-1]))))

Solution (Python):

import sys
from math import ceil

def solve(N: int):
    if N == 0:
        print(0)
        return 

    answer = ""
    while N != 0:
        syou = ceil(N/-2) 
        amari = N-syou*-2

        answer+= str(amari)
        N = syou
    
    print(answer[::-1])

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    solve(N)

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
ans = [0]*41
answer = ""
def finder(n):
    global ans
    if n == 0:
        return 1
    elif n >= 1:
        for i in range(1,20):
            if n <= (4**i-1)//3:
                ans[2*(i-1)] = 1
                return finder(n-2**(2*(i-1)))
    else:
        for i in range(1,20):
            if n >= -2*(4**i-1)//3:
                ans[2*i-1] = 1
                return finder(n+2**(2*i-1))
finder(N)
flg = False
for i in range(len(ans)):
    if ans[-(i+1)] == 1:
        flg = True
    if flg:
        answer += str(ans[-(i+1)])
if not flg:
    answer ="0"
print(answer)

Solution (Python):
n = int(input())
list1 = []

chinpo = 1

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

while True:
    if n==0:
        break
    if n%2 != 0:
        n -=1
        list1.append(1)
    else:
        list1.append(0)
    n /= -2

list1.reverse()
print("".join(map(str,list1)))

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

Solution (Python):
n=int(input())
if n==0:print(0)
k=-2
bi=''
while n!=0:
    bi+=str(n%abs(k))
    if k<0:n=-(-n//k)
    else:n=n//k
print(bi[::-1])

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

Solution (Python):

N = int(input())

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

Solution (Python):
import math
N= int(input())
ans = []
if N == 0:
    print(0)
else:
    for i in range(10**9):
        ans.append(str(abs(N%-2)))
        N = math.ceil(N/-2)
        if N == 1:
            break
    ans.append("1")
    ans2 = [ans[-i] for i in range(1, len(ans) + 1)]
    print("".join(ans2))

Solution (Python):
N = int(input())
A = []
if N == 0:
  A = [0]
i = 0
while N != 0:
  A = [N % 2] + A[:]
  N //= 2
  N = -N
for i in range(len(A)):
  print(A[i], end = '')

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

Solution (Python):
from collections import deque

N = int(input())
mod = 2
sign = 1
stack = deque()

while True:
    if N % mod != 0:
        stack.append("1")
        N -= mod // 2 * sign
    else:
        stack.append("0")
    mod *= 2
    sign *= -1
    
    if N == 0:
        break

for i in range(len(stack)):
    print(stack.pop(), end="")

Solution (Python):
n = int(input())
al = []
if n == 0:
  print("0")
else:
  while n:
    if n % 2 != 0:
      n -= 1
      al.append("1")
    else:
      al.append("0")
    n /= -2
  al.reverse()
  print("".join(al))

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

a = INT()

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

ans = ''
while abs(a) > 0:
    
    if a % 2 == 1:
        
        a -= 1
        ans += '1'
    else:
        ans += '0'
    
    a /= -2
print(ans[::-1])

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

a = INT()

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

ans = ''
i = 0
while abs(a) > 0:
    
    if a % 2**(i+1) != 0:
        a -= (-2)**i
        ans += '1'
    else:
        ans += '0'
    i += 1
print(ans[::-1])

Solution (Python):

import sys
input = sys.stdin.readline

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

print(ret)

Solution (Python):
N=int(input())
r=[]
x=0
while N!=0:
  d=abs(N)%2
  r.append(d)
  N=(N-d*(-1)**x)//2
  x+=1
print(*[0] if r==[] else r[::-1],sep='')

Solution (Python):
n = int(input())
s = "1" if n % 2 == 1 else "0"
n = - n // - 2
while n:
  mod = (n % 2) ** 2
  s = "{}".format(mod) + s
  n = n // - 2
print(s)

Solution (Python):
n=int(input())
ans=[]
if n==0:
    print(0)
else:
    while n!=0:
        if n%-2==0:
            n=n//-2
            r=0
            ans.append('0')
        if n%-2==-1:
            n=n//-2+1
            r=1
            ans.append('1')
    print(''.join(reversed(ans)))

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

answer = ""
for i in range(100):
  if N % 2 ** (i+1):
    answer += "1"
    N -= (-2)**i
  else:
    answer += "0"
  if N == 0:
    break
print(answer[::-1])

Solution (Python):
n = int(input())
ans = []
for i in range(40):
  if i % 2 == 0:
    if n % 2 == 1:
      n -= 1
      n //= 2
      ans.append(1)
    else:
      n //= 2
      ans.append(0)
  else:
    if n % 2 == 1:
      n += 1
      n //= 2
      ans.append(1)
    else:
      n //= 2
      ans.append(0)
  if n == 0:
    break
ans.reverse()
print("".join(map(str, ans)))

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

if n == 0:
  print(0)

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

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

if n == 0:
  print(0)

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

Solution (Python):
n = int(input())
if n<0:
    x = abs(n*2)
else:
    x = n
for i in range(1,100):
    if x<=(4**i-1)//3:
        ord = 2*i-1
        break
dif = -x
ans = []
for i in range(ord-1,-1,-1):
    if i%2 == 0:
        if dif < -(2**i-1)//3:
            ans.append(1)
            dif += 2**i
        else:
            ans.append(0)
    else:
        if dif > 2*(2**(i-1)-1)//3:
            ans.append(1)
            dif -= 2**i
        else:
            ans.append(0)
if n<0:
    del ans[-1]
print(*ans,sep="")

Solution (Python):
N=int(input())
ls=[]
while True:
  ls.append(N%2)
  N=-(N//2)
  if N==0:
    break
print(*reversed(ls),sep="")

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def f(n):
    v = 0
    for i in range(60):
        if 1 << i & n:
            v += (-2)**i
    return v


def slv(N):
    v = N
    for i in range(60):
        b = 1 if 1 << i & v > 0 else 0
        if b and i % 2 != 0:
            v += 1 << (i+1)

    return v


def main():
    N = read_int()
    print(bin(slv(N))[2:])



if __name__ == '__main__':
    main()

Solution (Python):
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    bl = []
    while True:
        if n == 0:
            break
        else:
            bl.append(str(n & 1))
            n //= 2
            n *= -1
    bl.reverse()
    print("".join(bl) if len(bl) != 0 else 0)


if __name__ == '__main__':
    solve()

Solution (Python):
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    bl = []
    while True:
        if n == 0:
            break
        else:
            bl.append(str(n & 1))
            n //= 2
            n *= -1
    bl.reverse()
    print("".join(bl) if len(bl) != 0 else 0)


if __name__ == '__main__':
    solve()

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