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())
s=""
i = 1
if n == 0:
    print(0)

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

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

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

print(ans if (ans != '') else '0')

Solution (Python):
def getBaseM2Num(n):
  if n == 0:
    return 0
  
  
  base = 1
  b2 = []
  while n != 0:
    if n % (2*base) == 0:
      
      b2.insert(0,"0")
    else:
      
      b2.insert(0,"1")
      n -= base
      
    base *= -2

  return "".join(b2)


n = int(input())
print(getBaseM2Num(n))

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())
ans=""
if N==0:
    print(0)
    quit()
while(N):
    if (N-1)%(-2)==0:
        ans+="1"
        N-=1
        N//=(-2)

    else:
        ans+="0"
        N//=(-2)

print(ans[::-1])

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


ans = ''
while N:
    ans = str(abs(N%2)) + ans
    N = - (N//2)
print(ans or 0)

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


ans = ''
while N:
    ans = str(abs(N % (-2))) + ans
    N = - (N//2)
    

print(ans or 0)

Solution (Python):
def solve(string):
    n = int(string)
    base = [(-2)**i for i in range(40)]
    ans = ""
    for b in base:
        if n % abs(2 * b) >= abs(b):
            n -= b
            ans += "1"
        else:
            ans += "0"
        if n == 0:
            break
    return ans[::-1]


if __name__ == '__main__':
    print(solve(input()))

Solution (Python):
from math import ceil, log
from itertools import product


def solve(string):
    n = int(string)
    base = [2**i for i in range(1, 40)]
    inc = [(-2)**i for i in range(40)]
    ans = ""
    for b, i in zip(base, inc):
        if n % b >= b // 2:
            n -= i
            ans += "1"
        else:
            ans += "0"
        if n == 0:
            break
    return ans[::-1]


if __name__ == '__main__':
    print(solve(input()))

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

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

ans = []
if N == 0:
    ans.append('0')
else:
    while abs(N) > 0:
        t = N % 2
        ans.append(str(t))
        N = N - t
        N = N // -2
    ans.reverse()
print("".join(ans))

Solution (Python):
import math
N = int(input())
ans = []
if N == 0:
  ans.append('0')
else:
  i = 0
  while abs(N) > 0:
    t = N % 2
    ans.append(str(t))
    N = N - t
    N = N // -2
    i += 1
  ans.reverse()
print("".join(ans))

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








if n < 0:
    n *= -1
    sign = 0
else:
    sign = 1

b = list(map(int, list(bin(n)[2:])))[::-1] + [0] * 30
results = []
for i, v in enumerate(b[:-1]):
    up = b[i] // 2
    b[i] %= 2
    b[i + 1] += up
    if i % 2 == sign:
        if b[i]:
            b[i + 1] += 1
print(int("".join(map(str, b[::-1]))))

Solution (Python):
def minus_bit(x):
    ans=""
    if x==0:
        return 0
    while x!=0:
        if x%-2==0:
            ans+="0"
        else:
            ans+="1"
            x-=1
        x/=-2
    return ans[::-1]
print(minus_bit(int(input())))

Solution (Python):
def div_neg_2(a):
    if a>0:
        return -(a//2), a%2
    elif a==0:
        return 0,0
    else:
        if (-a) % 2 == 1:
            return ((-a)+1)//2,1
        else:
            return (-a)//2,0

N = int(input())

ans = ""
next_n = N
while True:
    div, rem = div_neg_2(next_n)
    ans += str(rem)
    if div == 0:
        break
    next_n = div
print(ans[::-1])

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

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

Solution (Python):
N = int(input())
i = 0
S = 'a'
if N == 0:
    S += '0'
while N != 0:
    if i % 2 == 0:
        if N % 2**(i+1) == 0:
            S += '0'
        else:
            N -= 2**i
            S += '1'
    else:
        if N % 2**(i+1) == 0:
            S += '0'
        else:
            N += 2**i
            S += '1'
    i += 1
print(S[:0:-1])

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

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

ans = []

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

if len(ans)==0:
    ans.append('0')
ans.reverse()
ans = ''.join(ans)
print(ans)

Solution (Python):
n=int(input())
s=[]
count=n
if n==0:
    s.append(0)
while n!=0:
    if n%2==1:
        s.insert(0,1)
        n=(1-n)//2
    else:
        s.insert(0,0)
        n=-n//2
ans=map(str,s)
print(''.join(ans))

Solution (Python):
n,i,a=int(input()),0,0
while n:
  r=(-2)**i
  if (n-r)%(-2*r)==0:
    a+=10**i;n-=r
  i+=1
print(a)

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

ans = "" 
if N == 0:
    ans = "0"

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

print(ans)

Solution (Python):
n,a,i=int(input()),0,0
while n:
  r=(-2)**i
  if (n-r)%(-2*r)==0:a+=10**i;n-=r
  i+=1
print(a)

Solution (Python):
n,ans,i=int(input()),0,0
while n!=0:
  r=(-2)**i
  if (n-r)%(-2*r)==0:ans+=10**i;n-=r
  i+=1
print(ans)

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

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

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

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

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

x = ""

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

print(x if x else 0)

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

if n == 0:
  print(0)
else:
  i = 1
  ans = ''
  while n != 0:
    pi = pow(-1, i-1) * pow(2, i)
    if n % pi == pi // 2:
      ans += '1'
      n -= pi // 2
    else:
      ans += '0'
    i += 1
  print(ans[::-1])

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

Solution (Python):
N=int(input())
if N==0:
    print(0)
    quit()
S=""
i=0
while(N):
    if (N-(-2)**i)%2**(i+1)==0:
        S+="1"
        N-=(-2)**i
    else:
        S+="0"
    i+=1
S=S[::-1]
I=False
t=0
for i in S:
    if i=="1":
        break
    else:
        t+=1
print(S[t:])

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


def convert(n):
    result = []
    while True:
        a = n // 2
        b = n % 2
        result.insert(0, b)
        if a == 0:
            break
        else:
            n = a
    return result


def sigma_1(m):
    Sum = 0
    for i in range(m):
        Sum += 2**i
    return Sum


def sigma_2(m):
    Sum = 0
    for i in range(m):
        Sum += 2**(2*i)
    return Sum


def sigma_3(m):
    Sum = 0
    for i in range(1, m+1):
        Sum += 2**(2*i-1)
    return Sum


if 0 <= N <= 1:
    print(N)
elif N > 1:
    digit = 3  
    while True:
        if 1 + sigma_2(digit//2) <= N <= sigma_2(digit//2+1):
            break
        digit += 2
    ans = N-(1+sigma_2(digit//2)) + 2**(digit-1)
    ans = convert(ans)
    idx = 0
    for k in ans:
        if idx % 2:
            if k == 0:
                ans[idx] = 1
            else:
                ans[idx] = 0
        idx += 1
    for j in ans:
        print(j, end="")
else:
    N *= -1
    digit = 2
    while True:
        if 1 + sigma_3(digit//2-1) <= N <= sigma_3(digit//2):
            break
        digit += 2
    ans = N-(1+sigma_3(digit//2-1)) + 2**(digit-1)
    ans = convert(ans)
    idx = 0
    for k in ans:
        if idx % 2:
            if k == 0:
                ans[idx] = 1
            else:
                ans[idx] = 0
        idx += 1
    for j in ans:
        print(j, end="")

Solution (Python):

import sys


def solve(N: int):
    if N == 0:
        print(0)
        return
    result = ""
    div = 2
    while N != 0:
        divided = N % div
        N -= divided
        if divided != 0:
            result = "1" + result
        else:
            result = "0" + result
        div *= -2
    print(result)
    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):
def main():
	N = int(input())
	current = N
	ans = ""
	while current != 0:
		if current % 2 == 0:
			ans = "0" + ans
		else:
			ans = "1" + ans
			current -= 1
		current //= -2

	if ans == "":
		ans = "0"

	print(ans)


if __name__ == '__main__':
    main()

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







while(1):
  if(N == 1):
    ans.append('1')
    break
  elif(N == 0):
    ans.append('0')
    break
  if(N%(-2) == -1): 
    ans.append('1')
    N = N//(-2) + 1
  else: 
    ans.append('0')
    N = N//(-2) 

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

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

s=""

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

print(s if  s != "" else "0")

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

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 = N // -2
print(ans)

Solution (Python):


import itertools
import collections
import bisect



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

    v = 2
    ans = []
    while N != 0:
        if N % v == 0:
            ans.append(0)
        else:
            N -= (v // 2)
            ans.append(1)

        v *= -2
    print(''.join(map(str, ans[::-1])))


if __name__ == '__main__':
    main()

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

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

ans=""
dic=["00","01","10","11"]
a=[0,1,-2,-1]

while N!=0:
    i=N%4
    ans=dic[i]+ans
    N-=a[i]
    N//=4
print(ans if ans[0]=="1" else ans[1:])

Solution (Python):
def solve(n):
    if n == 0:
        return "0"
    p = 2
    s = []
    while n != 0:
        if n % p == 0:
            s.append(0)
        else:
            n -= (p // 2)
            s.append(1)
        p *= -2
    return "".join(map(str, s[::-1]))

assert solve(-9) == "1011"
assert solve(123456789) == "11000101011001101110100010101"
assert solve(0) == "0"
n = int(input())
print(solve(n))

Solution (Python):
n=int(input())
s_rev=""
while n!=0:
    
    
    s_rev+=str(n%2)
    n=n//(-2)+n%2
    
s=""
for i in range(len(s_rev)):
    s+=s_rev[len(s_rev)-i-1]
if s=="":
    print("0")
else:
    print(s)

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

s = ''

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

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

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

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

Solution (Python):

import sys
import itertools
import collections
import functools
import math
from queue import Queue
INF = float("inf")


def solve(N: int):
    ans = []
    kari = 0
    p = 1                       
    for i in range(40):
        c = N & 1               
        if c == ((kari >> i) & 1):
            ans.append(0)
        else:
            ans.append(1)
            kari += p
        N >>= 1
        p *= -2

    if 1 in ans:
        i = ans[::-1].index(1)
        print(*ans[::-1][i:], sep="")
    else:
        print(0)
    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 = ''

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

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

def baseNeg2(N: int) -> str:
        negTwoL = [0]*32
        index = len(negTwoL)-1
        if N >=0:
            while index > -1:
                if N >= 2**index:
                    if index % 2 == 0:
                        negTwoL[index] += 1
                    else:
                        negTwoL[index] += 1
                        negTwoL[index+1] += 1
                    N -= 2**index
                index -= 1
        else:
            N=-N
            while index > -1:
                if N >= 2**index:
                    if index % 2 == 1:
                        negTwoL[index] += 1
                    else:
                        negTwoL[index] += 1
                        negTwoL[index+1] += 1
                    N -= 2**index
                index -= 1

        if N >= 0:
            flag = 1
            while flag:
                flag = 0
                index2 = 0
                while index2 < len(negTwoL)-2:
                    if negTwoL[index2] > 1:
                        flag = 1
                        if negTwoL[index2] % 2 == 0:
                            if negTwoL[index2+1] == 1:
                                negTwoL[index2+1] = 0
                            else:
                                negTwoL[index2+1] += 1
                                negTwoL[index2+2] += 1
                            negTwoL[index2] = 0
                        else:
                            if negTwoL[index2+1] == 1:
                                negTwoL[index2+1] = 0
                            else:
                                negTwoL[index2+1] += 1
                                negTwoL[index2+2] += 1
                            negTwoL[index2] = 1
                    index2 += 1
        else:
            flag = 1
            while flag:
                flag = 0
                index2 = 2
                while index2 < len(negTwoL):
                    if negTwoL[index2] > 1:
                        flag = 1
                        if negTwoL[index2] % 2 == 1:
                            if negTwoL[index2+1] == 1:
                                negTwoL[index2+1] = 0
                            else:
                                negTwoL[index2-1] += 1
                                negTwoL[index2-2] += 1
                            negTwoL[index2] = 0
                        else:
                            if negTwoL[index2+1] == 1:
                                negTwoL[index2+1] = 0
                            else:
                                negTwoL[index2+1] += 1
                                negTwoL[index2+2] += 1
                            negTwoL[index2] = 1
                    index2 += 1
        negTwoL.reverse()
        while True:
            if len(negTwoL) == 1:
                break
            else:
                if negTwoL[0] == 0:
                    del negTwoL[0]
                else:
                    break
        return "".join(list(map(str, negTwoL)))


print(baseNeg2(n))

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

Solution (Python):
N = int(input())
a = ''
n = 0
while N != 0:
    b = '0' if N % (2**(n + 1)) == 0 else '1'
    a += b
    N -= ((-2)**n) * int(b)
    n += 1
print(a[::-1] if a else 0)

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

ans = []
num = 0
while True:
    if N % (2**(num + 1)) == 0:
        b = 0
    else:
        b = 1
    ans.append(str(b))
    N = N - ((-2)**num) * b
    num += 1
    if N == 0:
        break
print(''.join(ans[::-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 s == "":
  print("0")
else:
  print(s)

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

Solution (Python):
N=int(input())
flag=1 if N>=0 else 0
newN=abs(N)
M=0
A=bin(newN)[2:]




for i in range(len(A)):
	position=-(i*2+flag+1)
	if position < -len(A):
		break
	else:
		
		if A[position]=='1':
			M+=2**(position*(-1)-1)
			newN+=2**(position*(-1)-1)
			A=bin(newN)[2:]
			
			
print(bin(newN|M)[2:])

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

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

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

Solution (Python):
def f(n):
    if n == 0 or n == 1:
        return str(int(n))
    res = n % 2
    return f((n - res)/(-2)) + str(int(res))


N = int(input())
print(f(N))

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

def dig(n):
    l = len(bin(abs(n)))-2
    l += int(n * ((-1)**l)>0)
    return l

def main(n):
    if n == 0:
        return "0"
    s = ""
    while n!=0:
        if n%2:
            s = "1" + s
            n -= 1
        else:
            s = "0" + s
        n //= -2
    return s

print(main(N))

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

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

Solution (Python):
import sys
import math
import fractions
from functools import reduce
from collections import Counter
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]  
def LF(): return [float(x) for x in sys.stdin.readline().split()]  
def LS(): return sys.stdin.readline().split()  
def MI(): return map(int, sys.stdin.readline().split())  
def II(): return int(sys.stdin.readline())  
def IS(): return input()  
def P(x): return print(x)
def C(x): return Counter(x)
def GCD_LIST(numbers):
    return reduce(fractions.gcd, numbers)


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

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

N = int(input())
anslist = []

if N == 0:
    print(0)
else:
    while N != 1:
        anslist.append(str(abs(N%2)))
        N = math.ceil(N/(-2))
    anslist.append('1')

print(''.join(anslist[::-1]))

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

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

even = True
S = ''
while abs(N) > 0:
    if N % 2 == 1:
        if even:
            N -= 1
        else:
            N += 1
        S = '1' + S
    else:
        S = '0' + S
    N //= 2
    even = not even

if len(S) == 0:
    print('0')
else:
    print(S)

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

judge = 0
counter = 0
list = []
while judge == 0:
	if N % 2 == 0:
		list.append(0)
		a = 0
	else:
		list.append(1)
		a = 1
	N -= a
	N = N //(-2)
	if N == 0:
		judge = 1
list.reverse()
for i in list:
	print(i,end="")

Solution (Python):



import bisect

N = int(input())

if N == 0:
    print(0)
else:
    plus = [2 ** x for x in range(0, 35, 2)]
    minus = [2 ** x for x in range(1, 35, 2)]
    
    cum_plus = [sum(plus[:x]) for x in range(1, len(plus))]
    cum_minus = [sum(minus[:x]) for x in range(1, len(minus))]
    
    flags = []
    answer = 0
    while answer != N:
        if N - answer > 0:
            insert_index = bisect.bisect_left(cum_plus, N - answer)
            flags.append(insert_index * 2)
            answer += plus[insert_index]
            cum_plus = cum_plus[:insert_index]
        else:
            insert_index = bisect.bisect_left(cum_minus, abs(N - answer))
            flags.append(insert_index * 2 + 1)
            answer -= minus[insert_index]
            cum_minus = cum_minus[:insert_index]
            
    output = [0] * (flags[0] + 1)
    for flag in flags:
        output[flag] = 1
     
    print(''.join([str(x) for x in output[::-1]]))

Solution (Python):
n = int(input())
i = 1
ans = ''
while n != 0:
    if n % i == 0 and n % (i * -2) != 0:
        n -= i
        ans += '1'
    else:
        ans += '0'
    i *= -2
if ans == '':
  print(0)
else:
  print(ans[::-1])

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')



N = 0


def set_inputs():
    global N
    N = get_int()
    return


def base_10_to_n(x, n):
    mod = x % n
    mod = abs(mod)
    div = (x - mod) // n
    if div == 0:
        return str(mod)
    return base_10_to_n(div, n) + str(mod)


def main():
    setrecursionlimit(100000)
    set_inputs()
    print(base_10_to_n(N, -2))
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


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


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


if __name__ == '__main__':
    main()

Solution (Python):
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq
import itertools
import operator


inf = float('inf')



N = 0


def set_inputs():
    global N
    N = get_int()
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    if N == 0:
        print(0)
        return
    n = N
    ans = []
    while n != 0:
        rem = n % 2
        n = (n - rem) // (-2)
        ans.append(rem)
    ans.reverse()
    print("".join(map(str, ans)))
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


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


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types):
    if len(types) == 1:
        return [types[0](input()) for _ in range(n)]
    return zip(*(
        [t(x) for t, x in zip(types, input().split())]
        for _ in range(n)
    ))


if __name__ == '__main__':
    main()

Solution (Python):
m=2**33//3;print(bin(int(input())+m^m)[2:])

Solution (Python):
m=0xaaaaaaaa;print(bin(int(input())+m^m)[2:])

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

Solution (Python):
import numpy as np


N = input()
N = int(N)

def make_base_list(N):
    base_list = []
    for i in range(100):
        if N == 0:
            break
        if abs(N) % 2 == 0:
            base_list.append(int(0))
        else:
            base_list.append(int(1))
            if i % 2 == 0:
                N -= 1
            else:
                N += 1
        N = int(N)
        N = N // 2

        
    
    return base_list

def base_list_to_str(list):
    list = list[::-1]
    return ''.join([str(n) for n in list])


if __name__ == '__main__':
    if N == 0:
        print(str(0))
    else:
        print(base_list_to_str(make_base_list(N)))

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

Solution (Python):
n=int(input())
if n==0:
  print(0)
  exit()
if n>0:
  x=list(map(int,bin(n)[2:]))
  x.reverse()
  y=[0]*(len(x)+3-len(x)%2)
  for i in range(len(x)):
    if i%2==1 and x[i]==1:
      y[i]+=1
      y[i+1]+=1
    elif i%2==0 and x[i]==1:
      y[i]+=1
  for i in range(len(y)):
    if i%2==0 and y[i]==2:
      y[i]=0
      y[i+1]+=1
      y[i+2]+=1
    elif i%2==1 and y[i]==2:
      y[i]=0
      y[i+1]-=1
  y.reverse()
  print(int("".join(map(str,y))))
  exit()
if n<0:
  x=list(map(int,bin(abs(n))[2:]))
  x.reverse()
  y=[0]*(len(x)+3-len(x)%2)
  for i in range(len(x)):
    if i%2==0 and x[i]==1:
      y[i]+=1
      y[i+1]+=1
    elif i%2==1 and x[i]==1:
      y[i]+=1
  for i in range(len(y)):
    if i%2==1 and y[i]==2:
      y[i]=0
      y[i+1]+=1
      y[i+2]+=1
    elif i%2==0 and y[i]==2:
      y[i]=0
      y[i+1]-=1
  y.reverse()
  print(int("".join(map(str,y))))
  exit()

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

Solution (Python):
N = int(input())
if N == 0:
  print(0)
else:
  ans = ''
  flag = False
  while flag == False:
    if N%2 == 0:
      ans = '0'+ans
      N = N/(-2)
    else:
      ans = '1'+ans
      N -= 1
      if N == 0:
        flag = True
      else:
        N = N/(-2)
  print(ans)

Solution (Python):
from sys import stdin
import numpy as np

N = int(stdin.readline().rstrip())
to4 = []
while N !=1 and N!=-1 and N!=0:
  
  if N%2==0:
    to4.append("0")
    N = N//(-2)
  else:
    to4.append("1")
    N = int((N-1)/(-2))
  

if N==1:
  to4.append("1")
elif N==0:
  to4.append("0")
else:
  to4.append("11")
to4 = to4[::-1]
ans = "".join(to4)
print(ans)

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

ans = ""

if n == 0:
  ans += "0"

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

Solution (Python):
N = int(input())
if N == 0:
    print("0")
    exit()
a = []

for i in range(1000000000):
    if N == 0:
        break
    else:
        if abs(N) % pow(2,i+1) != 0:
            a.append(1)
            N -= pow(-2,i)
        else:
            a.append(0)
        

s = 0
for i in range(len(a)):
    s += a[i] * pow(10,i)
print(s)

Solution (Python):
n = int(input())
if n == 0:
	print(0)
	exit()
res = ""
while True:
	if n == 0:
		break
	else:
		if n%2 == 0:
			res += '0'
		else:
			res += '1'
			n -= 1
		n //= -2
print(res[::-1])

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

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

print(ans)

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

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

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

s = ""

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

Solution (Python):
n=int(input())
a=True
if n==0:
    print(0)
    a=False

lst=[]
while a:
    if n%-2==-1:
        n=n//-2 +1
        lst.append(1)
    else:
        n=n//-2
        lst.append(0)
    if n==1 :
        lst.append(1)
        lst.reverse()
        print(int("".join(list(map(str,lst)))))
        break

Solution (Python):
def main():
    a = int(input())
    ans = ""

    if a == 0:
        print (0)
        return 
    while a != 0:
        ans += str(int(abs(a) % 2))
        if int(abs(a)) & 1:
            a -= 1
        a /= (-2)

    print (ans[::-1])

main()

Solution (Python):
N=int(input())
P=N
Q=0
R=0
L=''
if N==0:
    ans=0
else:
    while abs(P)>1:
        if P%2==0:
            Q=P/(-2)
            L+='0'
        else:
            Q=(P-1)/(-2)
            L+='1'
        P=Q
    if P==1:
        L+='1'
    else:
        L+='11'
    ans=L[::-1]
print(ans)

Solution (Python):
N=int(input())
l=[0] if N==0 else []
j=0

while sum(l[i]*(-2)**i for i in range(len(l)))!=N:
  if sum(l[i]*(-2)**i for i in range(len(l)))%((-2)**(j+1))==N%((-2)**(j+1)):
    l.append(0)
  else:
    l.append(1)
  j+=1
print(''.join(map(str,reversed(l))))

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