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):
N=10**6
l=[0]*(N+1)
for i in range(1,N+1):
    c=0
    x=i
    while x%2==0:
        c+=1
        x//=2
    l[i]=c
for i in range(N):
    l[i+1]+=l[i]
def nCr(n,r):
    if l[n]>l[r]+l[n-r]:
        return 0
    else:
        return 1
n=int(input())
A=list(input())
for i in range(n):
  	A[i]=int(A[i])
AA=[0]*(n-1)
flag=0
for i in range(n-1):
    AA[i]=abs(A[i+1]-A[i])
    if AA[i]==1:
        flag=1
if flag==0:
    for i in range(n-1):
        AA[i]//=2
ans=0
for i in range(n-1):
    ans=(ans+nCr(n-2,i)*AA[i])%2
if flag==1:
    print(ans)
else:
    print(ans*2)

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

am = [a[i] % 2 for i in range(n)]

tmp = 0
ans = am[0] % 2

for i in range(1, n):
    ind = 0
    k = (n-i) & -(n-i)
    while k > 1:
        k = k // 2
        ind += 1
    kk = i & -i
    while kk > 1:
        kk = kk // 2
        ind -= 1
    tmp += ind
    if tmp == 0:
        ans += am[i]
        ans %= 2

if ans == 1:
    print(1)
    exit()




if 1 in a:
    print(0)
else:
    b = [1 if a[i] == 2 else 0 for i in range(n)]
    tmp = 0
    ans = b[0] % 2
    for i in range(1, n):
        ind = 0
        k = (n-i) & -(n-i)
        while k > 1:
            k = k // 2
            ind += 1
        kk = i & -i
        while kk > 1:
            kk = kk // 2
            ind -= 1
        tmp += ind
        if tmp == 0:
            ans += b[i]
            ans %= 2
    if ans == 1:
        print(2)
    else:
        print(0)

Solution (Python):
n = int(input())
a = list(map(lambda x: int(x)-1, input()))

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

def comb(k):
    left = cnt[n-1]
    right = cnt[k]+cnt[n-1-k]
    return left-right == 0

f = 1 in a
if f:
    a = [int(i==1) for i in a]
else:
    a = [int(i==2) for i in a]

ans = 0
for i in range(n):
    if comb(i):
        ans += a[i]

ans %= 2
if not f:
    ans *= 2

print(ans)

Solution (Python):
N = int(input())
a = list(map(int, list(input())))

while N != 0:
	digit = 1
	while digit < N // 2:
		digit *= 2

	x = []
	for i in range(digit, N):
		x.append(abs(a[i - digit] - a[i]))

	a = x
	N -= digit
	if len(x) == 1:
		break

print(a[0])

Solution (Python):
def ord(N,n):
    if n%N!=0:
        return 0
    else:
        return 1+ord(N,n//N)

N=int(input())
A=input()
A=[int(A[i]) for i in range(0,N)]
X=[abs(A[i]-A[i+1]) for i in range(0,N-1)]


cmb=[0 for i in range(0,N-1)]
cmb[0]=0
for i in range(1,N-1):
    cmb[i]=cmb[i-1]+ord(2,N-2-(i-1))-ord(2,i)
data=[0 for i in range(0,N-1)]
for i in range(0,N-1):
    if cmb[i]>0:
        data[i]=0
    else:
        data[i]=1

s=0
for i in range(0,N-1):
    s=(s+X[i]*data[i])%2
if s==1:
    print(1)
else:
    if 1 in X:
        print(0)
    else:
        X=[X[i]//2 for i in range(0,N-1)]
        s=0
        for i in range(0,N-1):
            s=(s+X[i]*data[i])%2
        if s==1:
            print(2)
        else:
            print(0)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9+7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))




def nCk(n):
    num = [0]*(n+1)
    for i in range(n+1):
        now = 2
        while now <= i:
            num[i] += i//now
            now *= 2
    
    
    
    ret = [0]*(n+1)
    for i in range(n+1):
        if num[n] > num[i]+num[n-i]:
            ret[i] = 0
        else:
            ret[i] = 1
    return ret

N = I()

A = list(input())
a = [0]*N
for i in range(N):
    a[i] = int(A[i])

b = [0]*(N-1)
for i in range(N-1):
    b[i] = abs(a[i]-a[i+1])

flag = False
for i in range(N-1):
    if b[i] == 1:
        flag = True
        break

nlist = nCk(N-2)

ans = 0
if not flag:
    for i in range(N-1):
        ans += nlist[i]*b[i]
        ans %= 4
    print(ans)
    
else:
    for i in range(N-1):
        ans += nlist[i]*(b[i]%2)
        ans %= 2
    print(ans)

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

    N = int(input())
    A = input().rstrip('\n')
    A = [int(a) for a in A]

    A = [abs(A[i+1] - A[i]) for i in range(N-1)]
    flg = 1
    if 1 not in A:
        flg = 2
        A = [a // 2 for a in A]
    else:
        A = [a % 2 for a in A]
    idx = []
    N -= 1
    for j in range(N.bit_length()):
        if N>>j&1:
            M = 2**j
            X = N%(M*2)
            if not idx:
                idx = list(range(M))
            else:
                idx_new = [X-1 - x for x in idx]
                idx.extend(idx_new)
    ans = 0
    
    
    for i in idx:
        ans ^= A[i]
    print(ans * flg)


if __name__ == '__main__':
    main()

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N=I()
    a2=input()
    a=[]
    for i in range(len(a2)):
        a.append(int(a2[i]))
    
    def calc(L):
        L1=list(L)
        nL=len(L)
        if nL%2==1 or nL<=5000:
            for i in range(nL-1):
                L1[i]=abs(L[i]-L[i+1])
            L1.pop()
                
            return L1
        else:
            L2=[]
            for i in range(0,nL,2):
                L2.append(abs(L[i]-L[i+1]))
            return L2

    while len(a)!=1:
        a=calc(a)    
    
    print(a[0])
                
        
    
main()

Solution (Python):
import sys

N = int(input())
S = input().strip()
ss = []
for c in S:
    ss.append(int(c))
if N == 2:
    print(abs(ss[0]-ss[1]))
    sys.exit()

X = []
X2 = []
fff = 0
for i in range(N-1):
    c = abs(ss[i] - ss[i+1])
    X.append(c%2)
    X2.append((c//2)%2)
    if c == 1:
        fff = 1


N=N-2

i = 0
Y = []
while N:
    if N%2:
        Y.append(i)
    i += 1
    N=N//2

C = [0]
for y in Y[::-1]:
    y = 2**y

    tmp = []
    for c in C:
        tmp.append(c+y)
    for t in tmp:
        C.append(t)
r = 0
r2 = 0
for c in C:
    r = r^X[c]
    r2 = r2^X2[c]
if fff:
    print(r)
else:
    print(r2*2)

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

N=int(input())
A=list(map(int,list(input().strip())))

def next(A):
    B=[]
    for i in range(1,len(A)):
        B.append(abs(A[i]-A[i-1]))
    return B

A=next(A)

if len(A)<=3:
    while len(A)>1:
        A=next(A)
    print(A[0])
    sys.exit()

def in2(x):
    if x==0:
        return 0
    ANS=0
    while x%2==0:
        ANS+=1
        x//=2
    return ANS


if not (1 in A):
    LEN=len(A)
    SUM=0
    COMBI=0

    for i in range(LEN):
        if COMBI==0:
            SUM+=A[i]//2

        COMBI=COMBI+in2(LEN-1-i)-in2(i+1)

    if SUM%2==1:
        print(2)
    else:
        print(0)
else:
    LEN=len(A)
    SUM=0
    COMBI=0

    for i in range(LEN):
        if COMBI==0:
            SUM+=A[i]

        COMBI=COMBI+in2(LEN-1-i)-in2(i+1)

    if SUM%2==1:
        print(1)
    else:
        print(0)

Solution (Python):
N = int(input())
A = list(map(int, input()))

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

Solution (Python):

import sys
import random
input = sys.stdin.readline

n = int(input())
s = input().rstrip()
a = [int(ch) for ch in s]


def naive(a):
    c = a[:]
    while len(c) > 1:
        b = []
        for c1, c2 in zip(c, c[1:]):
            b.append(abs(c1 - c2))
        c = b[:]
    return c[0]

def solve(a):
    c = a[:]
    while len(c) > 1:
        b = []
        if len(c) % 2 == 0:
            for c1, c2 in zip(c[::2], c[1::2]):
                b.append(abs(c1 - c2))
        else:
            for c1, c2 in zip(c, c[1:]):
                b.append(abs(c1 - c2))
        c = b[:]
    return c[0]

b = []
for a1, a2 in zip(a, a[1:]):
    b.append(abs(a1 - a2))
if 1 not in b:
    tmp = []
    for item in b:
        if item == 2:
            tmp.append(1)
        else:
            tmp.append(0)
    ret = solve(tmp)
    if ret == 1:
        print(2)
    else:
        print(0)
else:
    tmp = []
    for item in b:
        if item == 2:
            tmp.append(0)
        else:
            tmp.append(item)
    ret = solve(tmp)
    print(ret)

Solution (Python):
N=int(input())-1
a=input()
l=[None]*N
for i in range(N):
    l[i]=abs(int(a[i+1])-int(a[i]))
for i in range(19,0,-1):
    if N>2**i:
        t=2**i
        N-=t
        lb=[None]*N
        for i in range(N):
            if l[i+t//2]==1 and l[i]+l[i+t]==2:
                lb[i]=0
            else:
                lb[i]=abs(l[i]-l[i+t])
        l=lb
if len(l)==1:
    print(l[0])
else:
    print(abs(l[0]-l[1]))

Solution (Python):
import sys
input = sys.stdin.readline
def pr2(x):
  ret = 0
  while x%2 == 0:
    ret += 1
    x //= 2
  return ret
n = int(input())
s = input()
x = []
flg = 0
if s.count("2") >= 1:
  for i in range(n-1):
    t = abs(int(s[i+1])-int(s[i]))
    x.append(t%2)
else:
  flg = 1
  for i in range(n-1):
    t = abs(int(s[i+1])-int(s[i]))
    x.append(t//2)
n -= 1
num2 = 0
ans = 0
for i in range(n):
  if i == 0:
    ans += x[i]
    continue
  num2 += pr2(n-i)-pr2(i)
  if num2>0:
    continue
  else:
    ans += x[i]
if ans%2:
  print(flg+1)
else:
  print(0)

Solution (Python):
import sys
from itertools import product
readline = sys.stdin.readline

N = int(readline())
A = list(map(int, readline().strip()))
A1 = [a%2 for a in A]
for i in range(31, -1, -1):
    if (1<<i) & len(A1):
        k = 1<<i
        B = []
        B.append(sum(A1[:k])%2)
        for j in range(k, len(A1)):
            B.append((B[-1] + A1[j] - A1[j-k])%2)
        A1 = B[:]
    if (1<<i) & len(A1):
        k = 1<<i
        B = []
        B.append(sum(A1[:k])%2)
        for j in range(k, len(A1)):
            B.append((B[-1] + A1[j] - A1[j-k])%2)
        A1 = B[:]
pari = A1[0]
if pari == 1:
    ans = 1
else:
    if 2 in A:
        ans = 0
    else:
        A2 = [abs(a2-a1)//2 for a1, a2 in zip(A, A[1:])]
        N2 = len(A2)
        for i in range(31, -1, -1):
            if (1<<i) & len(A2):
                k = 1<<i
                B = []
                B.append(sum(A2[:k])%2)
                for j in range(k, len(A2)):
                    B.append((B[-1] + A2[j] - A2[j-k])%2)
                A2 = B[:]
            if (1<<i) & len(A2):
                k = 1<<i
                B = []
                B.append(sum(A2[:k])%2)
                for j in range(k, len(A2)):
                    B.append((B[-1] + A2[j] - A2[j-k])%2)
                A2 = B[:]
        
        if A2[0] == 0:
            ans = 0
        else:
            ans = 2

print(ans)

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












































ans = 0

if s.count("2") == 0:
    
    for i in range(n):
        if s[i] == "3":
            
            if (n-1)&i == i:
                ans += 1
    
    print(2 * (ans%2))
else:
    for i in range(n):
        if s[i] == "2":
            
            if (n-1)&i == i:
                ans += 1
    print(ans%2)

Solution (Python):
import math
import fractions

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 ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 5 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)





n = int(input())
s = input()
a = []

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

non1 = 1
for i in range(n):
    a.append(int(s[i])-1)
    if(a[i]==1):
        non1 = 0
total=0

if(non1==0):
    for i in range(n):
        total += is2(n-1,i)*(a[i]%2)
    print(total%2)
               
else:
    for i in range(n):
        total += is2(n-1,i)*(a[i]//2)
    print((total%2)*2)

Solution (Python):
def kezl(xlist):
    lenx=len(xlist)
    news=[]
    for i in range(lenx-1):
        news.append(abs(xlist[i+1]-xlist[i]))
    return news

flist=[]

import math
n=int(input())
alist=input()
blist=[]
swit=0
for i in range(n-1):
    now=abs(int(alist[i+1])-int(alist[i]))
    if now==1:
        swit=1
    blist.append(now)

if swit==1:
    for i in range(n-1):
        if blist[i]==2:
            blist[i]=0
    
    dekai=100
    while len(blist)>1:
        clist=[]
        dekai=math.floor(math.log(len(blist),2))
        katamari=2**dekai
        kosu=len(blist)-katamari+1
        nanko=0
        for i in range(katamari):
            if blist[i]==1:
                nanko+=1
        clist.append(nanko%2)
        for i in range(kosu-1):
            nanko+=blist[katamari+i]-blist[i]
            clist.append(nanko%2)
        blist=clist
        
    print(blist[0])
else:
    for i in range(n-1):
        if blist[i]==2:
            blist[i]=1
    
    dekai=100
    while len(blist)>1:
        clist=[]
        dekai=math.floor(math.log(len(blist),2))
        katamari=2**dekai
        kosu=len(blist)-katamari+1
        nanko=0
        for i in range(katamari):
            if blist[i]==1:
                nanko+=1
        clist.append(nanko%2)
        for i in range(kosu-1):
            nanko+=blist[katamari+i]-blist[i]
            clist.append(nanko%2)
        blist=clist
        
    print(blist[0]*2)

Solution (Python):
def pascal_parity(N):
    if N & -N == N:
        return [1] * N
    else:
        n = N - (1<<(N.bit_length()-1))
        p = pascal_parity(n)
        return p + [0]*(N-2*n) + p

N = int(input())
A = list(map(lambda x: int(x)-1, input()))
P = pascal_parity(N)
if 1 in A:
    if sum(a*p for a,p in zip(A, P)) % 2 == 1:
        print(1)
    else:
        print(0)
else:
    pa = 0
    for p, a in zip(P, A):
        if p==1 and a==2:
            pa += 1
    if pa % 2 == 1:
        print(2)
    else:
        print(0)

Solution (Python):






import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
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 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 lcm(a, b):
    return a * b // gcd (a, b)





N = inputI()
s_ = list(inputS())

s=[]
for i in range(len(s_)-1):
  s.append(abs(int(s_[i])-int(s_[i+1])))
N = N-1

def decode(s):
  
  N = len(s)
  news = []
  if set(s)!={0,2}:
    for n in range(20):
      if ((N-1)>>n)&1:
        d = pow(2,n)
        for i in range(N-d):
          news.append(abs(s[i]%2-s[i+d]%2))
        break
  else:
    for n in range(20):
      if ((N-1)>>n)&1:
        d = pow(2,n)
        for i in range(N-d):
          news.append(abs(s[i]-s[i+d]))
        break
    
  return news

  
while len(s) > 1:
  s = decode(s)

print(s[0])

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = list(map(int, read().decode().rstrip()))

U = N + 10
fact_ord = [0] * U
for n in range(1,U):
    fact_ord[n] = fact_ord[n//2] + (n//2)

def solve_01(A):
    ret = 0
    N = len(A) - 1
    comb_ord = [fact_ord[N] - fact_ord[i] - fact_ord[N-i] for i in range(N+1)]
    return sum(x * (y==0) for x,y in zip(A, comb_ord)) % 2

def solve(A):
    if len(A) == 1:
        return A[0]
    A = [abs(x - y) for x,y in zip(A, A[1:])]
    if all(x != 1 for x in A):
        B = [x // 2 for x in A]
        return 2 * solve_01(B)
    
    A = [x % 2 for x in A]
    return solve_01(A)

print(solve(A))

Solution (Python):
N = int(input())
A = [int(a) for a in input()]
def pascal_parity(n):
    def cnt2(m):
        a = m & -m
        return a.bit_length() - 1
    S = [0] * (n+1)
    for i in range(1, n):
        S[i] = S[i-1] + cnt2(n+1-i) - cnt2(i)
    return [1 if s == 0 else 0 for s in S]

def calc(L):
    return [abs(L[i] - L[i-1]) for i in range(1, len(L))]

def calc_all(L):
    for i in range(len(L)-1):
        L = calc(L)
    return L[0]

if N <= 5:
    print(calc_all(A))
else:
    A = calc(A)
    pp = pascal_parity(N-2)
    s = sum([a * pp[i] for i, a in enumerate(A)])
    if 1 in A:
        print(s % 2)
    else:
        print(s % 4)

Solution (Python):
n = int(input())
a = input()
b = []
att = 1
for i in range(n):
  b.append(int(a[i])-1)

for i in range(n):
  if b[i] % 2 == 1:
    break
else:
  att = 2
  for i in range(n):
    b[i] //= 2
for i in range(n):
  if b[i] == 2:
    b[i] = 0

pre = [0 for _ in range(10**6)]
now = 2
while now < 10**6 + 5:
  for k in range(10**6):
    try:
      pre[k*now] += 1
    except:
      now *= 2
      break

nm = [0]
for i in range(1,n):
  nm.append(nm[-1]-pre[i]+pre[n-i])
for i in range(n):
  if nm[i]:
    nm[i] = 0
  else:
    nm[i] = 1

ans = 0
for i in range(n):
  ans ^= b[i]*nm[i]
print(ans*att)

Solution (Python):

def solve_base(n, a_list):
    
    
    factorial_count_2 = [0] * n
    for i in range(1, n):
        p = i
        cnt = 0
        while p % 2 == 0:
            p = p // 2
            cnt += 1
        factorial_count_2[i] = factorial_count_2[i - 1] + cnt

    mod_2 = 0
    for i in range(n):
        if factorial_count_2[n - 1] == factorial_count_2[i] + factorial_count_2[n - 1 - i]:
            mod_2 += a_list[i] % 2
            mod_2 %= 2

    return mod_2


def solve(n, a_list):
    if 2 in a_list:
        return solve_base(n, a_list)
    else:
        return 2 * solve_base(n - 1, [abs(a_list[i] - a_list[i + 1]) // 2 for i in range(n - 1)])


def main():
    n = int(input())
    a_list = list(map(int, list(input())))
    res = solve(n, a_list)
    print(res)


def test():
    assert solve(4, [1, 2, 3, 1]) == 1
    assert solve(10, [2, 3, 1, 1, 3, 1, 2, 3, 1, 2]) == 0
    


if __name__ == "__main__":
    test()
    main()

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read


n = int(input())
a = [int(i) for i in input()]

n -= 1
d = [abs(i-j) for i,j in zip(a,a[1:])]

p2 = [0]
for i in range(1,n+2):
    r = p2[-1]
    while i&1==0:
        r += 1
        i >>= 1
    p2.append(r)    

def choose(n,k):
    if p2[n] > p2[k]+p2[n-k]: return 0
    else: return 1



par = sum(choose(n-1,i)*di for i, di in enumerate(d))%2

if par == 1:
    print(1)
else:
    if 1 in d: print(0)
    else:
        d = [di>>1 for di in d]
        par = sum(choose(n-1,i)*di for i, di in enumerate(d))%2
        
        if par == 0:
            print(0)
        else:
            print(2)