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
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


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

if __name__ == "__main__":
	main()

Solution (Python):
def digit_transform(N):
    if N == 0:  return "0"
    ans = ""
    while(N != 0):
        if N % -2 == 0:
            ans = "0" + ans
        else:
            ans = "1" + ans
            N -= 1
        N /= -2
    return ans

print(int(digit_transform(int(input()))))

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

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

s = ""

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

print(s[::-1])

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

if N == 0:
    print(0)
    exit()
elif N == 1:
    print(1)
    exit()
DP = [(0,1)]
num = 0
start = 0
end = 1
while True:
    num += 1
    a = end - start + 1
    if num % 2 == 0:
        start_ = end + 1
        end_ = start_ + a - 1
        end = end_
    else:
        end_ = start - 1
        start_ = end_ - a + 1
        start = start_
    DP.append((start_, end_))
    if start <= N <= end:
        break

Ans = ''
DP[0] = (1, 1)
for i, (start, end) in enumerate(DP[::-1]):
    if start <= N <= end:
        Ans += '1'
        N -= (-2) ** (num-i)
    else:
        Ans += '0'

print(Ans)

Solution (Python):
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    """
    Nを-2べきで展開したときの末端項がmod 2で決定できるから
    末尾から再帰的に桁が決められたのか。。。
    """
    N = int(input())
    if N == 0:
        print(0)
        return
    idx = 0
    ans = deque([])
    while N != 0:
        if N % 2 == 0:
            ans.appendleft(0)
        if N % 2 != 0:
            ans.appendleft(1)
            N -= (-1) ** idx
        N //= 2
        idx += 1
    print("".join(map(str, ans)))    

if __name__ == "__main__":
    main()

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

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

ans=''
while n!=0:
  r=n%(-2)
  if r<0:
    r+=2

  ans+=str(r)

  n-=r
  n//=(-2)

print(ans[::-1])

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()

def first_bit_of(n):
    """
    nの先頭ビットが下から何桁目かを出力する。（最下位を0桁目として）
    """
    if n == 0: return 0
    if n > 0:
        idx = 0
        while n > 0:
            n -= pow(4, idx)
            idx += 1
        return 2 * (idx - 1)
    if n < 0:
        idx = 0
        while n < 0:
            n += pow(2, 2 * idx + 1)
            idx += 1
        return 2 * idx - 1
        

def main():
    N = int(input())
    if N == 0:
        print(0)
        return
    first_place = first_bit_of(N)
    
    ans = [0] * (first_place + 1)
    ans[0] = 1
    N -= pow(-2, first_place)

    while N != 0:
        place = first_bit_of(N)
        
        ans[first_place - place] = 1
        N -= pow(-2, place)
    print("".join(map(str, ans)))
    

if __name__ == "__main__":
    main()

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

    if N is 0:
        print(0)
        return

    ans = []  
    while N:
        q, r = divmod(N, 2)
        ans.append(r)
        N = -q
    print(*reversed(ans), sep='')


if __name__ == '__main__':
    main()

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

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

ans=''
while n!=0:
  q=n%(-2)
  if q<0:
    q+=2

  ans+=str(q)

  n-=q
  n//=(-2)

print(ans[::-1])

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

A= [(-2)**i for i in range(40)]

ans=""

for i,num in enumerate(A):
    if N%((-2)**(i+1))==0:
        ans += "0"
    else:
        ans += "1"
        N -= num
    if N==0:
        break
print(ans[::-1])

Solution (Python):
from collections import deque
N = int(input())
tmp = N
ans = deque()
while tmp != 0:
  r = tmp % 2
  ans.appendleft(r)
  tmp = (tmp-r)//(-2)
print(0 if N == 0 else "".join([str(a) for a in ans]))

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

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

s = ""

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

print(s[::-1])

Solution (Python):
N = int(input())
num = N
bit = []
for i in range(1,10000):
    r = abs(num%2)
    bit.append(str(r))
    num = (num-r)//-2
    if num == 0 :
        break
bit.reverse()
print(''.join(bit))

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

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    if n == 0:
        print(0)
        exit()
    bit = []
    i = 0
    base = 1
    while n != 0:
        if n % (base * 2) == 0:
            bit.append("0")
        else:
            bit.append("1")
            n -= base
        i += 1
        base *= -2
    print("".join(bit[::-1]))


if __name__ == '__main__':
    resolve()

Solution (Python):
N = int(input())
sec = [1,-2]
for i in range(2,32):
  if i%2 == 0:
    sec.append(sec[i-2]+pow(2,i))
  else:
    sec.append(sec[i-2]-pow(2,i))

sec.reverse()
sec.append(0)
sec.append(0)
ans = []
for i in range(32):
  temp = 0
  if N >0 and sec[i] >0:
    if N>sec[i+2]:
      temp = 1
      
      N -= pow(-2,31-i)
  elif N<0 and sec[i] <0:
    if N < sec[i+2]:
      temp = 1
      
      N -= pow(-2,31-i)      
  ans.append(str(temp))

T = "".join(ans)
print(int(T))

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

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

Solution (Python):
n = int(input())
ans = []
for i in range(100):
    if n%(2**(i+1))>0:
        ans.append('1')
        n -= (-2)**i
    else:
        ans.append('0')
    if n==0:
        break
print(''.join(ans[::-1]))

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

ans = ""
cnt = 0

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

if not ans:
    print("0")
else:
    print(ans)

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

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

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

ans = []
while N != 0:
    d = len(ans)
    if N % 2 == 1:
        ans.append('1')
        N -= pow(-1, d)
        N //= 2
    else:
        ans.append('0')
        N //= 2

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

Solution (Python):
n = int(input())
ans = []
now = n
cou = 1
if n == 0:
    print(0)
    exit()
while True:
    if now == 0:
        break
    if now % (2**cou) == 2**(cou-1):
        ans.append(1)
        now -= (-2)**(cou-1)
    elif now % (2**cou) == 0:
        ans.append(0)
    cou += 1

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

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

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

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

print(ans_rev[::-1])

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N = getN()

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

cnt = 0
rep = N
lista = []





while rep != 0:
    split = (abs(rep) % 2 ** (cnt + 1)) // 2 ** cnt
    if split == 0:
        lista.append(0)
    else:
        lista.append(1)
    rep -= (split * ((-2) ** cnt))
    cnt += 1
lista.reverse()
print(''.join(map(str, lista)))

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N = getN()

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

cnt = 0
rep = abs(N)
lista = []

while rep != 0:
    split = (rep % 2 ** (cnt + 1)) // 2 ** cnt
    if split == 0:
        lista.append(0)
    else:
        lista.append(1)
    if N * (-1) ** cnt < 0:
        rep += (split * (2 ** cnt))
    else:
        rep -= (split * (2 ** cnt))
    cnt += 1
lista.reverse()
print(''.join(map(str, lista)))

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

def helper(x):
    if x == 0:
        return []
    r = x % (-2)
    return [r] + helper((x - r) // (-2))


tmp = helper(n)

ans = ''
carry = 0
for x in tmp:
    xx = x + carry
    if xx == -1:
        ans += '1'
        carry = 1
    elif xx == 0:
        ans += '0'
        carry = 0
    elif xx == 1:
        ans += '1'
        carry = 0
if carry:
    ans += '1'

if n == 0:
    print(0)
else:
    ans = str(int(ans[::-1]))
    print(ans)

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())


ans = []
of = 0


if N < 0:
    N = -N
    s = "0000" + bin(N)[2:]
    l = len(s)
    for i in range(l):
        
        of, b = of, int(s[l - i - 1])
        if i % 2 == 0:
            if (of, b) == (0, 0):
                ans.append(0)
                of = 0
            elif (of, b) == (0, 1):
                ans.append(1)
                of = 1
            elif (of, b) == (1, 0):
                ans.append(1)
                of = 1
            else:
                ans.append(0)
                of = 1
        else:
            if (of, b) == (0, 0):
                ans.append(0)
                of = 0
            elif (of, b) == (0, 1):
                ans.append(1)
                of = 0
            elif (of, b) == (1, 0):
                ans.append(1)
                of = 0
            else:
                ans.append(0)
                of = 1
    ans.reverse()
    pre_ans = "".join(list(map(str, ans)))
    print(pre_ans[pre_ans.find("1"):])

elif N > 0:
    s = "0000" + bin(N)[2:]
    l = len(s)

    for i in range(l):
        
        of, b = of, int(s[l - i - 1])
        if i % 2 == 0:
            if (of, b) == (0, 0):
                ans.append(0)
                of = 0
            elif (of, b) == (0, 1):
                ans.append(1)
                of = 0
            elif (of, b) == (1, 0):
                ans.append(1)
                of = 0
            else:
                ans.append(0)
                of = 1
        else:
            if (of, b) == (0, 0):
                ans.append(0)
                of = 0
            elif (of, b) == (0, 1):
                ans.append(1)
                of = 1
            elif (of, b) == (1, 0):
                ans.append(1)
                of = 1
            else:
                ans.append(0)
                of = 1
    ans.reverse()
    pre_ans = "".join(list(map(str, ans)))
    print(pre_ans[pre_ans.find("1"):])
else:
    print(0)

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

ans = []
while n:
    r = n % 2
    if r < 0:
        r += 2
    ans.append(str(r))
    n = (n-r) // -2
ans.reverse()

if len(ans) == 0:
    print(0)
else:
    print("".join(map(str, ans)))

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=[[0,0] for i in range(48)]
lis[0]=[0,1]
sup=1
low=0
for i in range(1,48):
    
    lis[i][0]=low+(-2)**i
    lis[i][1]=sup+(-2)**i
    if i%2==1:
        low+=(-2)**i
    else:
        sup+=(-2)**i

x=47
table=[0 for i in range(48)]
while x>0:
    if lis[x][0]<=n<=lis[x][1]:
        table[x]=1
        n-=(-2)**x
    x-=1
if n==1:
    table[0]=1

u=sum(table)
if u==0:
    print(0)
    sys.exit()
goal=[]
y=0
sm=0
while sm<u:
    if table[y]==1:
        sm+=1
    goal.append(table[y])
    y+=1

print(''.join(list(map(str,list(reversed(goal))))))

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

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

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

if n == 0:
    print(0)
else:
    cnt, now = 1, 0
    ans = ''
    for i in range(100):
        if n == now:
            break
        if (n - now) % (2**(i + 1)) != 0:
            ans = ans + '1'
            now += pow(-2, i)
        else:
            ans = ans + '0'
    print(ans[::-1])

Solution (Python):
n = int(input())
if n==0:
    print('0')
    exit(0)
i = 1
s = []
while n!=0:
    if n%2**i>0:
        s.append('1')
        n -= (-2)**(i-1)
    else:
        s.append('0')
    i += 1
print(''.join(s[::-1]))

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

if N == 0:
    print(0)
else:
    s = ""
    while abs(N) > 0:
        m = N % (-2)
        if m != 0:
            s = "1" + s
        else:
            s = "0" + s
        N = (N+m) // (-2)
    print(s)

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

lt = [0 for _ in range(50)]
rt = [0 for _ in range(50)]

lt[0] = 1
rt[0] = 1
lt[1] = -2
rt[1] = -1

for i in range(2, 50):
    if i % 2 == 0:
        lt[i] = rt[i - 2] + 1
        rt[i] = lt[i] + 2**i - 1
    else:
        rt[i] = lt[i - 2] - 1
        lt[i] = rt[i] - 2**i + 1


res = [0 for _ in range(50)]
while N:
    for i in range(50):
        if lt[i] <= N <= rt[i]:
            res[~i] = 1
            N -= (-2)**i
            break
            
print(int(''.join(map(str, res))))

Solution (Python):
N = int(input())
i = 0
s = ""
while N != 1 and N != 0:
    a = (N+1)//(-2)+1
    m = N - (-2)*a
    s += str(m)
    N = a

s += str(N)

print(s[::-1])

Solution (Python):
n = int(input())
p = 1
ans = ""
for i in range(32):
    mod = n%(-2*p)
    if mod>0 and p<0:
        if -2*p>0: mod -= (-2*p)
        else: mod += (-2*p)
    if mod<0 and p>0:
        if -2*p>0: mod += (-2*p)
        else: mod -= (-2*p)
    if mod==p:
        ans += "1"
        n -= p
    else :
        ans += "0"
    p *= -2
ans = ans[::-1].lstrip("0")
if len(ans): print(ans)
else: print(0)

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

if(N % 2 == 0):
  S.append("0")

while N!= 0:
  j = 0
  while N % 2** (i+ 1) == 0:
    i+= 1
    j+= 1
  for k in range(max(j- 1, 0)):
    S.insert(0, "0")
  S.insert(0, "1")
  N-= (-2)** i
  
ans = ""

for i in range(len(S)):
  ans+= S[i]
  
print(ans)

Solution (Python):
n = int(input())
amari = 0
i = 0
result = []
while i <= 40:
  if i ==0:
   hoge =  n % 2
   if hoge ==1:
      result.append(1)
      amari = 1
      i += 1
   else:
    result.append(0)
    i += 1
  else:
    hoge = n % (2**(i+1))
    if (amari + (-2)**(i)) % (2**(i+1)) == hoge:
      result.append(1)
      amari = amari + (-2)**(i)
      i += 1
    else:
      result.append(0)
      i += 1
      
result = result[::-1]
if n == 0:
  print(0)
else:
  s = ""
  check = False
  for r in result:
    if r == 0 and check == True:
      s += str(r)
    if r == 1:
      s += str(r)
      check = True
  print(int(s))

Solution (Python):
N = int(input())
out = []
U = 0
D = 0
t = 1
now = 0

if N>0:
    while now!=N:
        X = (N-D)%(2**t)
        if X!=0 and X<=(2**t)//2:
            out.append(1)
        else:
            out.append(0)
        if t%2==1:
            D += 2**(t-1)
        now = 0
        for i in range(len(out)):
            now += out[i]*(-2)**i
        t+=1
if N<0:
    while now!=N:
        X = (U-N)%(2**t)
        if X!=0 and X<=(2**t)//2:
            out.append(1)
        else:
            out.append(0)
        if t%2==0:
            U += -1*2**(t-1)
        now = 0
        for i in range(len(out)):
            now += out[i]*(-2)**i
        t+=1
if N==0:
    out = [0]

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

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

ans = ''
m = 2
i = 0

while 1:
  if N % m != 0:
    ans += '1'
    N = N - (-2)**i
  else:
    ans += '0'
  m *= 2
  i += 1
  if N == 0:
    break

print(ans[::-1])

Solution (Python):
N=int(input())
ans=''
a=-2
r=abs(N%a)
q=(N-r)//a
while q!=0:
  ans=str(r)+ans
  N=q
  r=abs(N%a)
  q=(N-r)//a
ans=str(r)+ans
print(ans)

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

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

ans=[]
if(n==0):
    print(0)
    exit()


while n!=0:
    r=n%2
    ans.append(r)
    n=int((n-r)/(-2))

ans.reverse()

for i in ans:
    print(i,end='')

Solution (Python):

N = int(input())


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

r_bits = ""
p = 0
d = 0
while N + p:
    if (N & 1) ^ p:
        r_bits += '1'
        if d ^ p:
            p ^= 1
    else:
        r_bits += '0'
    N >>= 1
    d ^= 1

print(r_bits[::-1])

Solution (Python):
import sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


n = int(input())
ans = ""
cnt = 0
if n == 0:
    print(0)
else:
    while True:
        if n == (-2) ** cnt:
            ans += "1"
            break
        if n % (-2) ** (cnt + 1) == 0:
            ans += "0"
        else:
            ans += "1"
            n -= (-2) ** cnt
        cnt += 1
        
        
    print(ans[::-1])

Solution (Python):
import sys
N = int(sys.stdin.readline().rstrip())
s = []
if N == 0:
    print(0)
    exit()
base = 1
cur = 2
while N != 0:
    r = N % cur
    if r > 0:
        s.append("1")
        N -= base
    else:
        s.append("0")
    cur *= 2
    base *= -2
print("".join(s[::-1]))

Solution (Python):
import sys
N = int(sys.stdin.readline().rstrip())
s = []
if N == 0:
    print(0)
    exit()
base = 1
cur = 2
while N != 0:
    r = N % cur
    r = r + cur if r < 0 else r
    if r > 0:
        s.append("1")
        N -= base
    else:
        s.append("0")
    cur *= 2
    base *= -2
print("".join(s[::-1]))

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 = ''
p = -2
while n!=0:
    n,r = divmod(n,p)
    if r < 0:
        r -= p
        n += 1
    ans = str(r) + ans
if ans == '': ans = '0'
print(ans)

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

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

Solution (Python):
def mainusbin(num):
    base = -2
    dst = ""
    i = 0
    if abs(base) > abs(num):
        return num
    while abs(base**i) <= abs(num):
        i += 1
        amari = num % base**i
        if amari:
            dst = "1" + dst
            num -= base**(i-1)
        else:
            dst = "0" + dst
    return dst
src = int(input())
dst = mainusbin(src)
print(dst)

Solution (Python):
def resolve():
	n = int(input())
	if n == 0:
		print("0")
		return
	out = ""
	base = 1
	while n != 0:
		if n % (-2) == 0:
			out = "0" + out
		else:
			r = n % (-2)
			if r < 0:
				r = 1
			n -= r
			out = "1" + out
		n /= (-2)


	print(out)
resolve()

Solution (Python):



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

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

if __name__ == "__main__":
    main()

Solution (Python):
def resolve():
	n = int(input())
	if n == 0:
		print("0")
		return
	out = []
	while n != 0:
		n, rem = divmod(n, -2)
		if rem < 0:
			n += 1
			rem -= -2
		out.append(rem)
	print("".join(map(str, out[::-1])))
resolve()

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

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

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

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

Solution (Python):
N=int(input())
ans=""
for i in range(1,10000):
   tmp=2**i
   if N%tmp==2**(i-1):
      N-=(-2)**(i-1)
      ans="1"+ans
   else:
      ans="0"+ans
   if N == 0:
      break
print(ans)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def Yes(): print("Yes"); return
def No(): print("No"); return


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def Base_10_to_n(X, n):
  if (int(X/n)):
    return Base_10_to_n(int(X/n), n)+[X%n]
  return [X%n]






N = inputI()


if N >= 0:
  b = Base_10_to_n(N, 2)[::-1]

  ans = [0] * 100
  n = len(b)

  for i in range(n):
    if b[i] == 1:
      if i == 0:
        ans[0] = 1
      else:
        if i%2:
          if ans[i] == 1:
            ans[i] = 0
            continue
          ans[i] += 1
          ans[i+1] += 1
          if ans[i] == 2:
            ans[i] = 0
            ans[i+1] = 1
            ans[i+2] = 1
        else:
          ans[i] += 1
          if ans[i] == 2:
            ans[i] = 0
            ans[i+1] = 1
            ans[i+2] = 1
else:
  b = Base_10_to_n(-N, 2)[::-1]

  ans = [0] * 100
  n = len(b)

  for i in range(n):
    if b[i] == 1:
      if i%2 == 0:
        if ans[i] == 1:
          ans[i] = 0
          continue
        ans[i] += 1
        ans[i+1] += 1
        if ans[i+1] == 2:
          ans[i+1] = 0
          ans[i+2] = 1
          ans[i+3] = 1
      else:
        ans[i] += 1
        if ans[i] == 2:
          ans[i] = 0
          ans[i+1] = 1
          ans[i+2] = 1
  
ans = [str(i) for i in ans]
print(int("".join(ans[::-1])))

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

def F(N):
  if(N == 0):
    return ''
  
  if(N % 2 == 0):
    return F(N//-2) + '0'
  else:
    return F((N-1)//-2) + '1'

if(N == 0):
  print(0)
else:
  print(F(N))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement, dropwhile
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18


def base10to(n, b):  
    if n == 0:
        return "0"
    ret = []
    while n != 0:
        r = n % b
        if r < 0:
            r += abs(b)
        n = (n-r)//b
        ret.append(str(r))
    return "".join(reversed(ret))

n = I()
print(base10to(n, -2))

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def F(x):
    if x == 0:
        return ''
    if x % 2 == 0:
        return F(x//-2) + '0'
    else:
        return F((x-1)//-2) + '1'

N = ir()
answer = F(N)
if N == 0:
    answer = 0
print(answer)

Solution (Python):
N = int(input())
i=abs(N)
lis = [0 for i in range(150)]
ind= 0
if i>0:
    while i>0:
        am = i%4
        i = i//4
        if N>0:
            lis[ind]=am
            lis[ind+1]=0
        else:
            lis[ind]=am
            lis[ind+1]=am
        ind+=2

ind=0
for i in range(148):
    
    if lis[i]==2:
        lis[i]=0
        lis[i+1]+=1
        lis[i+2]+=1
    elif lis[i]==3:
        lis[i]=1
        lis[i+1]+=1
        lis[i+2]+=1
    elif lis[i]>=4:
        lis[i+2]+=lis[i]//4
        lis[i]%=4

lis.reverse()
if N!=0:
    fir = lis[50:].index(1)
    map = map(str,lis[fir:])
    tmp = ''.join(map)
    print(int(tmp))
else:
    print(0)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    new_s=""
    i=0
    if n==0:
        print(0)
        sys.exit()
    while n:
        x=(n>>i)&1
        new_s=str(x)+new_s
        n-=x*(-2)**i
        i+=1
    print(new_s)


if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    new_s=""
    i=0
    if n==0:
        print(0)
        sys.exit()
    while n:
        x=(n>>i)&1
        new_s=str(x)+new_s
        n-=x*(-2)**i
        i+=1
    print(new_s)


if __name__=='__main__':
    main()