Problem:
 Score : 700 points    Problem Statement Given is a sequence of N digits a_1a_2\ldots a_N , where each element is 1 , 2 , or 3 .
Let x_{i,j} defined as follows:   x_{1,j} := a_j  \quad ( 1 \leq j \leq N )  x_{i,j} := | x_{i-1,j} - x_{i-1,j+1} |  \quad ( 2 \leq i \leq N and 1 \leq j \leq N+1-i )   Find x_{N,1} .      Constraints  2 \leq N \leq 10^6  a_i = 1,2,3  (1 \leq i \leq N)         Input Input is given from Standard Input in the following format:  N  a_1 a_2 \ldots a_N       Output Print x_{N,1} .        Sample Input 1 4
1231      Sample Output 1 1  x_{1,1},x_{1,2},x_{1,3},x_{1,4} are respectively 1,2,3,1 .  x_{2,1},x_{2,2},x_{2,3} are respectively |1-2| = 1,|2-3| = 1,|3-1| = 2 .  x_{3,1},x_{3,2} are respectively |1-1| = 0,|1-2| = 1 .  Finally, x_{4,1} = |0-1| = 1 , so the answer is 1 .       Sample Input 2 10
2311312312      Sample Output 2 0

Solution (Python):
def solve_for_01(nums):
    
    
    
    
    
    
    
    N = len(nums)
    ans = 0
    for i, x in enumerate(nums):
        if (N - 1) & i == i:
            ans ^= x
    return ans


def main():
    
    N = int(input())
    A = list(map(lambda x: int(x) - 1, input()))
    if 1 in A:
        
        
        print(solve_for_01([a % 2 for a in A]))
    else:
        
        
        print(solve_for_01([a // 2 for a in A]) * 2)


if __name__ == '__main__':
    main()

Solution (Python):

n=int(input())
a=list(map(lambda x:int(x)-1,list(input())))
memo=[-1]*(n+1)
def log(x):
    if memo[x]!=-1:return memo[x]
    ret=0
    xx=x
    while x and x%2==0:
        x//=2
        ret+=1
    memo[xx]=ret
    return ret

def slv(n,a):
    v=a[0]
    if all(v==x for x in a):return 0
    
    chk=0
    tmppl=0
    tmpmi=0
    for i in range(n):
        x=a[i]%2
        if tmppl>tmpmi:
            pass
        else:
            chk+=a[i]
            chk%=2
        tmppl+=log(n-i-1)
        tmpmi+=log(i+1)
    if chk:return 1
    if 1 in a:return 0
    a=[x//2 for x in a]
    return slv(n,a)*2
print(slv(n,a))

Solution (Python):
N = int(input())
S = ''.join([str(int(d) - 1) for d in input()])

def solve01(s):
    "solve the problem when 's' consists of 0 or 1"
    ans = 0
    for k, d in enumerate(s):
        if k & (N - 1) == k:
            ans ^= int(d)
    return ans      

if '1' in S: 
    print(solve01(S.replace('2', '0')))
else: 
    print(solve01(S.replace('2', '1')) * 2)

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


def solve(n, s):
    sub = [int(s[i])-1 for i in range(n)]
    
    table = [0]*(n+1)
    p = 2
    for i in range(len(bin(n))-1):
        for j in range(p, n+1, p):
            table[j] += 1
        p *= 2
    
    for i in range(n):
        table[i+1] += table[i]
    
    ans = 0
    for i in range(n):
        if sub[i]%2:
            judge = table[n-1]-table[n-1-i]-table[i]
            if not judge:
                ans += 1
    
    
    if ans%2:
        res = 1
    else:
        if 1 in sub:
            res = 0
        else:
            res = 0
            for i in range(n):
                if sub[i]:
                    judge = table[n-1]-table[n-1-i]-table[i]
                    if not judge:
                        res += 1
            return res%2*2
    
    return res
    
    
def main():
    n = int(input())
    s = input()
    
    ans = solve(n, s)
    print(ans)
    
    
if __name__ == "__main__":
    main()

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


def solve(n, s):
    sub = [int(s[i])-1 for i in range(n)]
    
    table = [0]*(n+1)
    p = 2
    for i in range(len(bin(n))-1):
        for j in range(p, n+1, p):
            table[j] += 1
        p *= 2
    
    for i in range(n):
        table[i+1] += table[i]
    
    ans = 0
    for i in range(n):
        if sub[i]%2:
            judge = table[n-1]-table[n-1-i]-table[i]
            if not judge:
                ans += 1
    
    
    if ans%2:
        res = 1
    else:
        if 1 in sub:
            res = 0
        else:
            res = 0
            for i in range(n):
                if sub[i]:
                    judge = table[n-1]-table[n-1-i]-table[i]
                    if not judge:
                        res += 1
            return res%2*2
    
    return res
    
    
def main():
    n = int(input())
    s = input()
    
    ans = solve(n, s)
    print(ans)
    
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict


input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  
  
from functools import lru_cache





n=int(input())
s=input()
A=[int(i)-1 for i in s]

RUI2=[pow(2,i) for i in range(21)]
import bisect as bi
@lru_cache(maxsize=10**10)
def tan(n):
    if n==0:return [1]
    if n==1:return [1,1]
    if n==2:return [1,0,1]
    i= bi.bisect_right(RUI2,n)-1
    return tan(n-pow(2,i)) + [0]*(pow(2,i+1)-n-1) + tan(n-pow(2,i))











if A.count(1)!=0:
    A=[i%2!=1 for i in A]
    a=[i&j for i,j in zip(A,tan(n-1))]
    
    print(1 if sum(a)%2==1 else 0)
else:
    a=[(i//2)&j for i,j in zip(A,tan(n-1))]
    
    print(2 if sum(a)%2==1 else 0)

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

fac2 = [0] * (n+1)
i = 2
while(i <= n ):
    for j in range(i,n+1,i):
        fac2[j] += 1
    i *= 2

for i in range(1,n+1):
    fac2[i] += fac2[i-1]

def calc(x):
    len_x = len(x)
    res = 0
    for i,xi in enumerate(x):
        if(fac2[len_x-1] - fac2[len_x-1-i] - fac2[i] > 0):
            continue
        res = res ^ xi
    return res

if(a.count('2')==0):
    x = []
    for ai in a:
        x.append(int(ai)//2)
    res = calc(x)
    if(res==0):
        print(0)
    else:
        print(2)
else:
    x = []
    for ai in a:
        x.append( (int(ai)-1) % 2)
    res = calc(x)
    print(res)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, list(input())[: -1]))
res = 0
rres = 0
for i in range(N):
  t = (((N - 1) & i) & i) == i
  res ^= t * a[i] % 2
  rres ^= t * (a[i] // 2) % 2
if (2 in a) and res == 0: print(0)
elif res == 1: print(1)
else:
  if rres: print(2)
  else: print(0)

Solution (Python):
n=int(input())
def f(n,r):
    return n==r|(n-r)
s=list(map(int,list(input())))
b=[]
for i in range(n-1):b.append(abs(s[i]-s[i+1]))
if (0 in b and len(set(b))==2) or len(set(b))==1:
    ans=0
    anss=0
    for i in range(n-1):
        if b[i]:
            anss=b[i]
            ans+=f(n-2,i)
    if ans%2==0:
        print(0)
    else:
        print(anss)
    quit()
ans=0
for i in range(n-1):
    if b[i]%2==1:
        anss=b[i]
        ans+=f(n-2,i)
if ans%2==0:
    print(0)
else:
    print(1)

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

N = int(input())
a = list(map(int, list(input()[:-1])))
a = list(map(lambda x: x-1, a))
p = [0]*N

for i in range(1, N):
    t = i
    
    while t%2==0:
        t //= 2
        p[i] += 1

for i in range(1, N):
    p[i] += p[i-1]

X = 0

for i in range(N):
    if a[i]==1 and p[N-1-i]+p[i]==p[N-1]:
        X += 1

if X%2==1:
    print(1)
else:
    if 1 in a:
        print(0)
    else:
        b = [ai//2 for ai in a]
        X = 0
        
        for i in range(N):
            if b[i]==1 and p[N-1-i]+p[i]==p[N-1]:
                X += 1
        
        print(2*(X%2))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd, sqrt
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint
from copy import deepcopy



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 2


n = I()
s = S()
l = len(s)
L = []
one_cnt = 0
for i in range(l - 1):
    ret = abs(int(s[i]) - int(s[i + 1]))
    L += [ret]
    if ret == 1:
        one_cnt += 1

m = 0
for j in range(l - 1):
    m += int(l - 2 & j == j) * L[j]
    m %= 2

if m % 2:
    print(1)
    exit()
else:
    if one_cnt:
        print(0)
    else:
        L = [k // 2 for k in L]
        ret2 = 0
        for jj in range(l - 1):
            ret2 += int(l - 2 & jj == jj) * L[jj]
            ret2 %= 2
        if ret2:
            print(2)
        else:
            print(0)

Solution (Python):
import sys
input = sys.stdin.readline
from functools import reduce
from itertools import starmap
from operator import xor, mul
N = int(input())
A = list(map(int ,input().strip()))

A = [abs(x-y) for x,y in zip(A,A[1:])]
n = len(A)

coef = [((n-1)&k)==k for k in range(n)]
if 1 in A:
    B = [x % 2 for x in A]
    ans = reduce(xor, starmap(mul, zip(B,coef)))
else:
    B = [x // 2 for x in A]
    ans = reduce(xor, starmap(mul, zip(B,coef)))*2

print(ans)

Solution (Python):

import sys
input = sys.stdin.readline
N = int(input())
A = list(input().rstrip())

def two_num(x):
    res = 0
    while x%2==0:
        x //= 2
        res += 1
    return res

C_twos = [0]*N
for i in range(1, N):
    res = C_twos[i-1] + two_num(N-i) - two_num(i)
    C_twos[i] = res

if '2' in A:
    ans = 0
    for i in range(N):
        ans ^= (int(A[i])-1)&1 * (C_twos[i]==0)
    print(ans)
else:
    ans = 0
    for i in range(N):
        ans ^= (int(A[i])-1)//2 * (C_twos[i]==0)
    print(ans*2)

Solution (Python):
n = int(input())
a = list(map(int, input()))
a = [e - 1 for e in a]


def cnt_div2(x):
    ret = 0
    while x % 2 == 0 and x != 0:
        x //= 2
        ret += 1

    return ret


now = 0
cnt = [0]
for i in range(1, n):
    now += cnt_div2(n - i)
    now -= cnt_div2(i)
    cnt.append(now)

div2 = [e == 0 for e in cnt]


def f(li):
    ret = 0
    for e1, e2 in zip(li, div2):
        e1 %= 2
        ret ^= e1 * e2

    return ret


if f(a):
    ans = 1

elif 1 in a:
    ans = 0

else:
    a = [e // 2 for e in a]
    if f(a):
        ans = 2
    else:
        ans = 0

print(ans)

Solution (Python):
n=int(input())
s=input()
a=[int(s[i])-1 for i in range(n)]

div=[0]*(n+1)
for i in range(1,n+1):
  div[i]+=div[i-1]
  x=i
  while not x&1:
    x>>=1
    div[i]+=1

XOR=0;one=False
for i in range(n):
  one|=a[i]==1
  if div[n-1]<=div[i]+div[n-1-i]:
    XOR^=a[i]
if XOR&1:print(1)
elif one:print(0)
elif XOR&2:print(2)
else:print(0)

Solution (Python):
n=int(input())
s=input()
a=[int(s[i])-1 for i in range(n)]

div=[0]*(n+1)
for i in range(1,n+1):
  div[i]+=div[i-1]
  x=i
  while not x&1:
    x>>=1
    div[i]+=1

XOR=0;one=False
for i in range(n):
  one|=a[i]==1
  if div[n-1]<=div[i]+div[n-1-i]:
    XOR^=a[i]
if XOR&1:print(1)
elif one:print(0)
elif XOR&2:print(2)
else:print(0)

Solution (Python):
n=int(input())
s=input()
a=[int(s[i])-1 for i in range(n)]

div=[0]*(n+1)
for i in range(1,n+1):
  div[i]+=div[i-1]
  x=i
  while not x&1:
    x>>=1
    div[i]+=1

XOR=0
for i in range(n):
  if div[n-1]<=div[i]+div[n-1-i]:
    XOR^=a[i]
if XOR&1:
  print(1)
  exit(0)


for i in a:
  if i==1:
    print(0)
    exit(0)

XOR=0
for i in range(n):
  if div[n-1]<=div[i]+div[n-1-i]:
    XOR^=a[i]>>1
if XOR&1:
  print(2)
  exit(0)
print(0)

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,cos,radians,sqrt
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()
s=list(map(int,SI()))
if n==1:
    print(s[0])
    sys.exit()

def divi2(x):
    if x%2==1:
        return 0
    else:
        count=0
        while x%2==0:
            x//=2
            count+=1
        return count

pw2=[0 for i in range(n-1)]
for i in range(n-1):
    if i%2==1:
        pw2[i]=divi2(i+1)


cmbnk2=[0 for i in range(n)]
for i in range(n-1):
    cmbnk2[i+1]=cmbnk2[i]+pw2[n-2-i]-pw2[i]

ans=0
'''if (s.count(1)==1 and not 2 in s ) or (s.count(3)==1 and not 2 in s ):
    ans=2
    print(ans)
    sys.exit()'''
if not 2 in s:
    for i in range(n):
        s[i]=(s[i]-1)//2
    for i in range(n):
        if cmbnk2[i]==0:
            ans+=s[i]%2
    if ans%2==0:
        print(0)
    else:
        print(2)
    sys.exit()
    
        
else:
    for i in range(n):
        if cmbnk2[i]==0:
            ans+=s[i]%2
            
        
        
print(ans%2)

Solution (Python):
f2=[0]*10**6
p2=2
while p2<10**6:
    for i in range(p2,10**6,p2):
        f2[i]+=1
    p2*=2
for i in range(1,10**6):
    f2[i]+=f2[i-1]

n=int(input())
s=input()

p = '2' if '2' in s else '3'

ans=0
for i,c in enumerate(s):
    if c==p:
        ans += 0 if f2[n-1]-f2[i]-f2[n-1-i] else 1
print(int(p)-1 if ans%2==1 else 0)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int1,input()))
    X=0
    c=0
    f=False
    if not 1 in a:
        for i in range(N):
            a[i]//=2
        f=True
    for i in range(N):
        if c==0:
            X^=a[i]%2
        K=N-1-i
        while K>0 and K%2==0:
            c+=1
            K//=2
        K=i+1
        while K>0 and K%2==0:
            c-=1
            K//=2
    if X==1:
        print(1*(f+1))
    else:
        print(0)

if __name__ == '__main__':
    main()

Solution (Python):



import numpy as np
n=int(input())
a_ = list(map(int, list(input())))
a = np.array(a_)-1
div2=[0]
cnt=0
ex1 = False

if 1 in a:
    ex1 = True
else:
    a//=2
tst=1
tsts=[1]
for i in range(n-1):
    cnt += bin(n-i-1)[::-1].find('1')
    cnt -= bin(i+1)[::-1].find('1')
    
    
    div2.append(cnt)
    tsts.append(tst)

div2=np.array(div2)
dv2=1-(div2>0)



tmp= (a*dv2).sum()%2
if tmp:
    if ex1:
        print(1)
    else:
        print(2)

else:
    print(0)

Solution (Python):
n = int(input())
a = list(map(lambda x:int(x)-1,input()))
ans = 0
for i in range(n):
    if (n-1) & i == i:
        ans += a[i]
if ans % 2 == 1:
    print(1)
else:
    if a.count(1) != 0:
        print(0)
    else:
        ans = 0
        b = list(map(lambda x:x//2,a))
        for i in range(n):
            if (n-1) & i == i:
                ans += b[i]
        if ans % 2 == 1:
            print(2)
        else:
            print(0)

Solution (Python):
n = int(input())
a = list(map(int, input()))
l = [0] * (n - 1)
for i in range(n - 1):
    l[i] = abs(a[i + 1] - a[i])
n -= 1
if 1 in l:
    for i in range(n):
        if l[i] == 2:
            l[i] = 0
ans = 0
for i, x in enumerate(l):
    if not (i ^ (n - 1)) & i:
        ans ^= x
print(ans)

Solution (Python):
import sys


def main():
    N = int(input())
    a = input()
    nl = []
    
    for num in a:
        num = int(num)
        nl.append(num-1)

    if 1 in nl:
        cnt = 0
        for i,num in enumerate(nl):
            cnt += num*(N-1 == i|((N-1)-i))
        print(cnt%2)
    else:
        for i in range(N):
            nl[i] //= 2
        cnt = 0
        for i,num in enumerate(nl):
            cnt += num*(N-1 == i|((N-1)-i))
        print((cnt%2)*2)

if __name__ == "__main__":
    main()

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

def fact_mod2(n,r):
  if n==(r|(n-r)):
    return 1
  else:
    return 0

alist=[]
for s in slist:
  alist.append(int(s)-1)  


parity=0
for i in range(N):
  parity+=fact_mod2(N-1,i)*alist[i]


if parity%2==1:
  print(1)
else:
  if 1 in alist:
    print(0)
  else:
    for i in range(N):
      alist[i]//=2
    
    parity=0
    for i in range(N):
      parity+=fact_mod2(N-1,i)*alist[i]
    if parity%2==1:
      print(2)
    else:
      print(0)

Solution (Python):

def twos_in_factorial(n):
    return n - bin(n).count('1')


def parity_of_nCr(n, i):
    """ if odd, return False. """
    f = twos_in_factorial
    return f(n) - f(n-i) - f(i) > 0


if __name__ == "__main__":
    n = int(input())
    nums = list(map(lambda x: int(x) - 1, input().strip()))
    no_one = False
    if 1 not in nums:
        nums = [num // 2 for num in nums]
        no_one = True

    is_odd = False
    for i, num in enumerate(nums):
        if not parity_of_nCr(n-1, i) and num & 1:
            is_odd ^= 1

    if not is_odd:
        print(0)
    else:
        print(1 << no_one)

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()
a = input()
a = list(map(lambda x:int(x)-1, list(a)))
b = [0 if i % 2 == 0 else i for i in a]
cnt = 0
for i in range(n):
    if b[i] % 2:
        if (n-1) & i == i:
            cnt += 1
if cnt % 2:
    print(1)
else:
    if 1 in b:
        print(0)
    else:
        c = [i // 2 if i % 2 == 0 else i for i in a]
        cnt = 0
        for i in range(n):
            if c[i] % 2:
                if (n-1) & i == i:
                    cnt += 1
        if cnt % 2:
            print(2)
        else:
            print(0)

Solution (Python):
import os
import sys

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())
A = list(map(int, sys.stdin.buffer.readline().decode().rstrip()))


def pp(A, offset=0):
    s = ' ' * offset + ' '.join(map(str, A))
    print(s)


def test(A):
    i = 0
    while len(A) > 1:
        pp(A, i)
        A = list(map(lambda a: abs(a[0] - a[1]), zip(A, A[1:])))
        i += 1
    pp(A, i)
    return A


def convert(counts):
    ret = []
    if counts[0][1] > 1:
        ret.append((0, counts[0][1] - 1))
    for (n1, cnt1), (n2, cnt2) in zip(counts, counts[1:]):
        ret.append((abs(n1 - n2), 1))
        if cnt2 > 1:
            ret.append((0, cnt2 - 1))

    n = None
    count = 0
    filtered = []
    for a, cnt in ret:
        if a != n:
            n = a
            count = 0
            filtered.append((n, 0))
        count += cnt
        filtered[-1] = (n, count)
    return filtered











cnt2 = []
cnt = 0
for n in range(N + 10):
    while n >= 2 and n % 2 == 0:
        n //= 2
        cnt += 1
    cnt2.append(cnt)


A = list(map(lambda a: abs(a[0] - a[1]), zip(A, A[1:])))

if 1 in A:
    for i in range(len(A)):
        if A[i] == 2:
            A[i] = 0
mod = 2 if 1 in A else 4

ans = 0
n = len(A) - 1
for r in range(len(A)):
    cnt = cnt2[len(A) - 1] - cnt2[r] - cnt2[n - r]
    
    if cnt == 0:
        ans += A[r]
        ans %= mod
    
print(ans)

Solution (Python):
n,a=int(input())-1,list(map(lambda x:int(x)-1,list(input())));b=[i%2for i in a]
def c(x):
 a=0
 for j,i in enumerate(x):a^=(n|j==n)*i
 return a
if c(b):k=1
elif 1in a:k=0
else:k=c([i//2for i in a])*2
print(k)

Solution (Python):
def main():
    n = int(input())
    a = list(map(lambda x: int(x)-1, list(input())))
    b = [i % 2 for i in a]

    def all_a(x):
        ans = 0
        for j, i in enumerate(x):
            ans ^= (n-1 | j == n-1)*i
        return ans

    all_b = all_a(b)
    if all_b == 1:
        print(1)
        return
    if 1 in a:
        print(0)
        return
    b = [i//2 for i in a]
    print(all_a(b)*2)


main()

Solution (Python):
def main():
    n = int(input())
    a = list(map(lambda x: int(x)-1, list(input())))
    b = [i % 2 for i in a]

    def all_a(x):
        ans = 0
        for j, i in enumerate(x):
            ans ^= (n-1 | j == n-1)*i
        return ans

    all_b = all_a(b)
    if all_b == 1:
        print(1)
        return
    if 1 in a:
        print(0)
        return
    b = [i//2 for i in a]
    print(all_a(b)*2)


main()

Solution (Python):
import math

N = int(input())
A = list(map(int,input()))
B = []

for i in range(N):
  if N-1 == (i|N-1-i):
    B.append(1)
  else:
    B.append(0)
    
b = 0
for i in range(N):
  b += B[i]*A[i]
if b % 2 == 1:
  print(1)
else:
  for i in range(N):
    if A[i] == 2:
      print(0)
      break
  else:
    c = 0
    for i in range(N):
      A[i] = (A[i]-1)//2
      c += B[i]*A[i]
    if c % 2 == 1:
      print(2)
    else:
      print(0)

Solution (Python):
n=int(input())
arr=list(input())
arr=[int(arr[i]) for i in range(n)]
if n==1:
  print(arr[0])
if n==2:
  print(abs(arr[0]-arr[1]))
else:
  tmp=[]
  for i in range(n-2):
    tmp.append(abs(abs(arr[i]-arr[i+1])-abs(arr[i+1]-arr[i+2])))
  arr=tmp
  while len(arr)>3:
    tmp=[]
    if len(arr)%2==0:
      for i in range(len(arr)//2):
        tmp.append(abs(arr[2*i]-arr[2*i+1]))
    else:
      for i in range(len(arr)-1):
        tmp.append(abs(arr[i]-arr[i+1]))
    arr=tmp
  if len(arr)==1:
    print(arr[0])
  elif len(arr)==2:
    print(abs(arr[0]-arr[1]))
  elif len(arr)==3:
    print(abs(abs(arr[0]-arr[1])-abs(arr[1]-arr[2])))

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

def lucas(n, k):
    return (n&k) == k

N = INT()
A = [a-1 for a in list(map(int, input()))]

def check(A):
    mod2 = 0
    for i, a in enumerate(A):
        if a == 1:
            mod2 += lucas(N-1, i)
            mod2 %= 2
    return mod2

res = check(A)
if res == 1:
    print(1)
    exit()

if A.count(1):
    print(0)
    exit()

A = [a//2 for a in A]
res = check(A)
if res == 1:
    print(2)
else:
    print(0)

Solution (Python):
N = int(input())
A = [int(a) - 1 for a in input()]

b = 1 if 1 in A else 2

ans = 0
for i, a in enumerate(A):
    if ((N - 1) & i) == i and (a ^ b) == 0:
        ans ^= b

print(ans)

Solution (Python):
import sys

N = int(input()) - 1
two = False
S = 0
for i in range(N+1):
  a = int(sys.stdin.read(1))
  if not two:
    two = a == 2
  if i & N == i:
    S ^= a-1

if two:
  S &= ~2

print(S)

Solution (Python):
import sys

N = int(input()) - 1
two = False
S = 0
for i in range(N+1):
  a = int(sys.stdin.read(1))
  two |= (a == 2)
  if i & N == i:
    S ^= a-1

if two:
  S &= ~2

print(S)

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n = ni()
l = list(map(lambda x:int(x) - 1, list(ns())))
f = 1
if 1 not in l:
    l = [x//2 for x in l]
    f += 1

def Cmod2(n, r):
    return n&r == r

s = sum(Cmod2(n-1,i)*l[i] for i in range(n)) % 2
print(f*s)

Solution (Python):
N = int(input())
A = [int(c)-1 for c in input()]
x = 0
b = 1 if any(a==1 for a in A) else 2
for k,a in enumerate(A):
    p = int(((N-1)&k)==k)
    if p and a^b==0:
        x ^= b
print(x)

Solution (Python):
def popcount_parity(x, a):
    x ^= x >> 2
    x ^= x >> 4
    x ^= x >> 8
    x ^= x >> 16
    x ^= x >> 32
    x ^= x >> 64
    x ^= x >> 128
    x ^= x >> 256
    x ^= x >> 512
    x ^= x >> 1024
    x ^= x >> 2048
    x ^= x >> 4096
    x ^= x >> 8192
    x ^= x >> 16384
    x ^= x >> 32768
    x ^= x >> 65536
    x ^= x >> 131072
    x ^= x >> 262144
    x ^= x >> 524288
    x ^= x >> 1048576
    return x & a

def include_2(a):
    x = (~a) & (a >> 1)
    x |= x >> 2
    x |= x >> 4
    x |= x >> 8
    x |= x >> 16
    x |= x >> 32
    x |= x >> 64
    x |= x >> 128
    x |= x >> 256
    x |= x >> 512
    x |= x >> 1024
    x |= x >> 2048
    x |= x >> 4096
    x |= x >> 8192
    x |= x >> 16384
    x |= x >> 32768
    x |= x >> 65536
    x |= x >> 131072
    x |= x >> 262144
    x |= x >> 524288
    x |= x >> 1048576
    return x & 1

N = int(input()) - 1 << 1
s = 1
while N:
    l = N & -N
    s |= s << l
    N ^= l

a = int(input(), 4)
if include_2(a):
    print(popcount_parity((~a) & s, 1))
else:
    print(popcount_parity(a & (s << 1), 2))

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

def is_combination_odd(n, r):
    _n = n
    _r = r
    is_odd = True
    while _n > 0 and _r > 0:
        if _n % 0b10 < _r % 0b10:
            is_odd = False
            break
        _n >>= 1
        _r >>= 1
    
    return is_odd
    
def is_ans_odd(num_str: str) -> bool:
    is_odd = False
    for i, c in enumerate(num_str):
        is_c_odd = int(c) % 2
        is_odd ^= is_combination_odd(len(num_str)-1, i) & is_c_odd
    return is_odd

def main():
    ans = -1
    table = str.maketrans({'1': '0', '2': '1', '3': '2'})
    a012 = a.translate(table)
    if is_ans_odd(a012):
        ans = 1
    else:
        if '1' in a012:
            ans = 0
        else:
            table = str.maketrans({'2': '1'})
            a01 = a012.translate(table)
            if is_ans_odd(a01):
                ans = 2
            else:
                ans = 0

    print(ans)

if __name__ == '__main__':
    main()

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

al = [int(a) - 1 for a in al]
flag = False
if 1 not in al:
    flag = True
    al = [a // 2 for a in al]
else:
    al = [a if a != 2 else 0 for a in al]

countl = [0]
a = 0
for i in range(1, n+1):
    while i % 2 == 0:
        a += 1
        i //= 2
    countl.append(a)

def comb(a,b):
    if countl[a] - countl[a-b] - countl[b] > 0:
        return 0
    else:
        return 1

ans = 0
for idx, a in enumerate(al):
    if a == 1:
        ans += comb(n-1, idx)


if ans % 2 == 0:
    print(0)
else:
    if flag:
        print(2)
    else:
        print(1)

Solution (Python):
def popcount_parity(x, a):
    x ^= x >> 2
    x ^= x >> 4
    x ^= x >> 8
    x ^= x >> 16
    x ^= x >> 32
    x ^= x >> 64
    x ^= x >> 128
    x ^= x >> 256
    x ^= x >> 512
    x ^= x >> 1024
    x ^= x >> 2048
    x ^= x >> 4096
    x ^= x >> 8192
    x ^= x >> 16384
    x ^= x >> 32768
    x ^= x >> 65536
    x ^= x >> 131072
    x ^= x >> 262144
    x ^= x >> 524288
    x ^= x >> 1048576
    return x & a

N = int(input()) - 1 << 1
s = 1
while N:
    l = N & -N
    s |= s << l
    N ^= l

A = input()
if "2" in A:
    a = ~int(A, 4)
    print(popcount_parity(a & s, 1))
else:
    a = int(A, 4)
    print(popcount_parity(a & (s << 1), 2))

Solution (Python):
n = int(input())
l = [int(s)-1 for s in input()] 

if 1 in l:
    s = 0
    for i,a in enumerate(l):
        s += a*(n-1 == (i|(n-1-i)))
    print(s%2)
else:
    l = [i//2 for i in l]
    s = 0
    for i,a in enumerate(l):
        s += a*(n-1 == (i|(n-1-i)))
    print(s%2*2)

Solution (Python):
def popcount_parity(x):
    x ^= x >> 1
    x ^= x >> 2
    x ^= x >> 4
    x ^= x >> 8
    x ^= x >> 16
    x ^= x >> 32
    x ^= x >> 64
    x ^= x >> 128
    x ^= x >> 256
    x ^= x >> 512
    x ^= x >> 1024
    x ^= x >> 2048
    x ^= x >> 4096
    x ^= x >> 8192
    x ^= x >> 16384
    x ^= x >> 32768
    x ^= x >> 65536
    x ^= x >> 131072
    x ^= x >> 262144
    x ^= x >> 524288
    return x & 1

N = int(input()) - 1
s = 1
while N:
    l = N & -N
    s |= s << l
    N ^= l

A = input()
if "2" in A:
    a = int(A.replace("1", "0").replace("3", "0").replace("2", "1"), 2)
    print(popcount_parity(a & s))
else:
    a = int(A.replace("1", "0").replace("3", "1"), 2)
    print(popcount_parity(a & s) * 2)

Solution (Python):
N=int(input())
a=[int(i)-1 for i in list(input())]
def solve(seq):
    if {0}==set(seq):
        return 0
    res=0
    for k in range(N):
        tmp=0
        if ((N-1)&k)==k:
            tmp=1
        
        res+=tmp*seq[k]
        res%=2
    
    if res%2==1:
        return 1
    if 1 in set(seq):
        return 0
    seq2=[seq[i]//2 for i in range(N)]
    return solve(seq2)*2
print(solve(a))

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

if "2" in a:
	ans = 0
	for i in range(n):
		if a[i] == "2":
			ans ^= ((n-1) == ( i | (n-1 - i)))
	if ans:
		print(1)
	else:
		print(0)

else:
	ans = 0
	for i in range(n):
		if a[i] == "3":
			ans ^= ((n-1) == ( i | (n-1 - i)))
	if ans:
		print(2)
	else:
		print(0)

Solution (Python):
N = int(input())
a = [ int(s) - 1 for s in input()]


twos = {}
twos[0] = 0
for r in range(1, N):

    count = 0
    tmp = r
    while tmp % 2 == 0:
        tmp //= 2
        count += 1
    
    twos[r] = twos[r-1] + count



ncr = {}
for r in range(N):
    if twos[N-1] - twos[N-1-r] - twos[r] > 0:
        ncr[r] = 0
    else:
        ncr[r] = 1



oe = 0
for r, ai in enumerate(a):
    oe = (oe + ncr[r] * ai) % 2

if oe == 1:
    print(1)
else:
    if 1 in a:
        print(0)
    else:
        oe2 = 0
        for r, ai in enumerate(a):
            oe2 = (oe2 +ncr[r] * ai // 2 ) %2
        if oe2 == 1:
            print(2)
        else:
            print(0)

Solution (Python):
def popcount_parity(x):
    x ^= x >> 1
    x ^= x >> 2
    x ^= x >> 4
    x ^= x >> 8
    x ^= x >> 16
    x ^= x >> 32
    x ^= x >> 64
    x ^= x >> 128
    x ^= x >> 256
    x ^= x >> 512
    x ^= x >> 1024
    x ^= x >> 2048
    x ^= x >> 4096
    x ^= x >> 8192
    x ^= x >> 16384
    x ^= x >> 32768
    x ^= x >> 65536
    x ^= x >> 131072
    x ^= x >> 262144
    x ^= x >> 524288
    return x & 1

N = int(input()) - 1
s = 1
while N:
    l = N & -N
    s *= 1 + (1 << l)
    N ^= l

A = input()
if "2" in A:
    a = int(A.replace("1", "0").replace("3", "0").replace("2", "1"), 2)
    print(popcount_parity(a & s))
else:
    a = int(A.replace("1", "0").replace("3", "1"), 2)
    print(popcount_parity(a & s) * 2)

Solution (Python):
def popcount_parity(x):
    x ^= x >> 1
    x ^= x >> 2
    x ^= x >> 4
    x ^= x >> 8
    x ^= x >> 16
    x ^= x >> 32
    x ^= x >> 64
    x ^= x >> 128
    x ^= x >> 256
    x ^= x >> 512
    x ^= x >> 1024
    x ^= x >> 2048
    x ^= x >> 4096
    x ^= x >> 8192
    x ^= x >> 16384
    x ^= x >> 32768
    x ^= x >> 65536
    x ^= x >> 131072
    x ^= x >> 262144
    x ^= x >> 524288
    return x & 1

N = int(input()) - 1
s = 1
while N:
    l = N & -N
    s *= 1 + (1 << l)
    N ^= l

A = input()
if "2" in A:
    a = int(A.replace("1", "0").replace("3", "0").replace("2", "1"), 2)
    print(popcount_parity(a & s))
else:
    a = int(A.replace("1", "0").replace("3", "1"), 2)
    print(popcount_parity(a & s) * 2)