Problem:
 Score : 500 points    Problem Statement  A cheetah and a cheater are going to play the game of Nim.
In this game they use N piles of stones.
Initially the i -th pile contains a_i stones.
The players take turns alternately, and the cheetah plays first.
In each turn, the player chooses one of the piles, and takes one or more stones from the pile.
The player who can't make a move loses.  However, before the game starts, the cheater wants to cheat a bit to make sure that he can win regardless of the moves by the cheetah.
From each pile, the cheater takes zero or one stone and eats it before the game.
In case there are multiple ways to guarantee his winning, he wants to minimize the number of stones he eats.  Compute the number of stones the cheater will eat.
In case there is no way for the cheater to win the game even with the cheating, print -1 instead.      Constraints  1 ≤ N ≤ 10^5  2 ≤ a_i ≤ 10^9         Input The input is given from Standard Input in the following format:  N  a_1 : a_N       Output Print the answer.        Sample Input 1 3
2
3
4      Sample Output 1 3  The only way for the cheater to win the game is to take stones from all piles and eat them.       Sample Input 2 3
100
100
100      Sample Output 2 -1

Solution (Python):
import math

n = int(input())
x = 0
s = [0] * 35
for _ in range(n):
    a = int(input())
    x ^= a
    s[int(math.log2(int((a ^ (a - 1)) + 1))) - 1] = 1
t = [0] * 35
while True:
    if x == 0:
        break
    y = int(math.log2(x))
    t[y] = 1
    x -= pow(2, y)
s.reverse()
t.reverse()
ans = 0
now = 0
for i in range(35):
    if now == t[i]:
        continue
    else:
        if s[i] == 1:
            ans += 1
            now = 1 - now
        else:
            print(-1)
            exit()
print(ans)

Solution (Python):
n = int(input())
a = [int(input()) for i in range(n)]
xora = 0
xorls = []
for i in a:
  xora ^= i
  xorls.append(i^(i-1))
xorls.sort(reverse=True)
ans = 0
for i in xorls:
  if xora == 0:
    break
  if xora.bit_length() == i.bit_length():
    xora ^= i
    ans += 1
if xora:
  print(-1)
else:
  print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
a = [0] * N
for i in range(N): a[i] = int(input())
table = [0] * N
for i in range(N):
  x = a[i]
  bn = list(bin(x)[2: ])
  bn.reverse()
  for j in range(len(bn)):
    if bn[j] == "1":
      table[i] = (1 << j) - 1 + (1 << j)
      break

xm = 0
for x in a: xm ^= x
table.sort(reverse = True)
res = 0
for x in table:
  if xm ^ x < xm:
    res += 1
    xm ^= x
if xm: print(-1)
else: print(res)

Solution (Python):
n = int(input())
a = [int(input()) for _ in range(n)]
s = set()
x = 0
for i in range(n):
    x ^= a[i]
    s.add(len(bin(a[i] & -a[i])) - 3)
res = 0
for i in range(50, -1, -1):
    if (x >> i) & 1:
        if i in s:
            x ^= (1 << (i + 1)) - 1
            res += 1
        else:
            print(-1)
            exit(0)
print(res)

Solution (Python):
import sys
input = sys.stdin.readline
read = sys.stdin.read
import numpy as np

n = int(input())
A = np.array(read().split(), dtype=np.int64)
m = 30
C = np.zeros(m, dtype=bool)
used = np.zeros(n, dtype=bool)
x = 0
for a in A:
  x ^= a
for i in range(m):
  idx = np.where(A>>i & 1)
  if np.any(~used[idx]):
    C[i] = True
  used[idx] = True
total = 0
ans = 0
for i in range(m-1, -1, -1):
  if (x>>i & 1) ^ total:
    if C[i]:
      ans += 1
      total ^= 1
    else:
      print(-1)
      break
else:
  print(ans)

Solution (Python):
n = int(input())
A = [int(input()) for _ in range(n)]
m = 30
C = [False]*m
x = 0
for a in A:
  x ^= a
  for i in range(m):
    if a>>i & 1:
      C[i] = True
      break
total = 0
ans = 0
for i in range(m-1, -1, -1):
  if (x>>i & 1) ^ total:
    if C[i]:
      ans += 1
      total ^= 1
    else:
      print(-1)
      break
else:
  print(ans)

Solution (Python):
n = int(input())
A = [int(input()) for _ in range(n)]
m = 30
C = [False]*m
x = 0
for a in A:
  x ^= a
  for i in range(m):
    if a>>i & 1:
      C[i] = True
      break
total = 0
ans = 0
for i in range(m-1, -1, -1):
  if (x>>i & 1) ^ total:
    if C[i]:
      ans += 1
      total ^= 1
    else:
      print(-1)
      break
else:
  print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
N=int(input())
ALL=0
bit=[0 for i in range(31)]

for i in range(N):
    a=int(input())
    ALL^=a
    B=100
    for j in range(31):
        if a//(2**(30-j))==1:
            B=j
        a%=(2**(30-j))
    bit[B]=1

all=[0 for i in range(31)]
for j in range(31):
    if ALL//(2**(30-j))==1:
        all[j]+=1
    ALL%=(2**(30-j))

cnt=0
ans=0
for i in range(31):
    if (all[i]+cnt)%2==1:
        if bit[i]>=1:
            ans+=1
            cnt+=1
        else:
            print(-1)
            exit()
print(ans)

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

ans = 0
for i in range(n):
    ans ^= a[i]

set_ = set()
for i in range(n):
    set_.add(a[i] ^ (a[i] - 1))
 
cnt = 0
for i in range(50)[::-1]:
    if ans & (1 << i):
        cnt += 1
        if (1 << (i + 1)) - 1 in set_:
            ans ^= (1 << (i + 1)) - 1
        else:
            print(-1)
            exit()
print(cnt)

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


N = int(input())
A = [int(input()) for _ in range(N)]

w = 0
for a in A:
    w ^= a

canuse = [True]*N

ans = 0
while w != 0:
    l = w.bit_length()-1
    use = -1
    for i, a in enumerate(A):
        if (1<<l)&a and canuse[i] and not (1<<l)&(a-1):
            canuse[i] = False
            use = a
            break
    if use == -1:
        ans = -1
        break
    ans += 1
    w = w ^ use ^ (use-1)
print(ans)

Solution (Python):
n = int(input())
a = [int(input()) for _ in range(n)]
t = 0
for x in a: t ^= x
s = set((x&-x).bit_length() for x in a)
cnt = 0
while t:
  if t.bit_length() in s:
    cnt += 1
    t ^= (1 << t.bit_length()) - 1
  else:
    print(-1)
    break
else: print(cnt)

Solution (Python):
def main():
    n = int(input())
    a = [int(input()) for _ in [0]*n]
    xor = 0
    for i in a:
        xor ^= i
    i = 1
    cnt = 0
    while True:
        if xor >= i:
            i *= 2
            cnt += 1
        else:
            break
    ans = 0
    for i in range(cnt-1, -1, -1):
        j = (xor & 2**i) // (2**i)
        if j == 1:
            for k in a:
                if (k & 2**i) // (2**i) == 1 and k % (2**i) == 0:
                    xor ^= k
                    xor ^= k-1
                    ans += 1
                    a.remove(k)
                    break
            else:
                print(-1)
                return 0
    print(ans)


main()

Solution (Python):

N = int(input())
lis = []
xor = 0

for i in range(N):

    a = int(input())
    xor ^= a

    now = 0

    while a % (2 ** now) == 0:
        now += 1

    lis.append(now-1)

lis.sort()
lis.reverse()


ans = 0

for i in lis:

    if xor == 0:
        break

    if xor >= (2 ** i) and xor ^ (2 ** (i+1) - 1) != xor:
        xor = xor ^ (2 ** (i+1) - 1)
        ans += 1



if xor == 0:
    print (ans)

else:
    print (-1)

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]

digits = set()

for a in A:
    digits.add((a & -a).bit_length() - 1)

xor = 0
for a in A:
    xor ^= a

ans = 0

for digit in range(xor.bit_length() + 1)[:: -1]:
    if (xor & (1 << digit)) > 0:
        if digit in digits:
            ans += 1
            xor ^= ((1 << (digit + 1)) - 1)
        else:
            print(-1)
            exit()

print(ans)

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]

A.sort(reverse=True, key=lambda a: (a & -a))

xor = 0
for a in A:
    xor ^= a

left = 0
ans = 0

for digit in range(xor.bit_length() + 1)[:: -1]:
    if (xor & (1 << digit)) > 0:
        while left < N and ((A[left] & -A[left]).bit_length() - 1) > digit:
            left += 1

        if left >= N or ((A[left] & -A[left]).bit_length() - 1) != digit:
            print(-1)
            exit()

        ans += 1
        xor ^= ((1 << (digit + 1)) - 1)

print(ans)

Solution (Python):
import sys

def I(): return(int(sys.stdin.readline()))
def IR(n): return([I() for _ in range(n)])

def main():
    N = I()
    A = IR(N)

    x = 0
    for a in A:
        x ^= a

    dic = {}
    for a in A:
        dic[a^(a-1)] = True
    
    ans = 0
    while(x!=0):
        y=0
        while ((1<<(y+1))<=x):
            y+=1
        if dic.get((1<<(y+1))-1,False):
            x^=((1<<(y+1))-1)
            ans += 1
        else:
            return(-1)
    return(ans)

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

Solution (Python):
def solve(n, a):
    """
    References
    ----------
    [1]. 足跡-sokuseki-, CODE FESTIVAL 2016 Grand Final C - Cheating Nim, http://wk1080id.hatenablog.com/entry/2018/08/17/234023
    [2]. iroiro, CODE FESTIVAL 2016 Grand Final C - Cheating Nim, http://xxxasdfghjk999.hatenablog.jp/entry/2018/11/01/235259
    [3]. Yang33, 競プロにおけるNim、Grundy数とNimK, http://yang33-kassa.hatenablog.com/entry/2017/12/21/202812
    """
    x = 0
    for i in range(n):
        x ^= a[i]
    b = [a[i] ^ (a[i] - 1) for i in range(n)]
    mapping = {2**k-1: 0 for k in range(31)}
    for y in b:
        mapping[y] += 1
    ans = 0
    for k in range(30, 0, -1):
        y = 2**k - 1
        z = 2**(k-1)
        if (x & z) > 0 and (mapping[y] > 0):
            ans += 1
            mapping[y] -= 1
            x ^= y
    return ans if x == 0 else -1

n = int(input())
a = [int(input()) for i in range(n)]
print(solve(n, a))

Solution (Python):
from collections import defaultdict


N = int(input())
D1 = defaultdict(int)
D2 = defaultdict(int)
A = 0
for i in range(N):
	a = int(input())
	A = A ^ a
	D1[a ^ (a - 1)] += 1


n = A.bit_length()
for i in range(n):
	if A >= 2 ** (n - i - 1):
		D2[2 ** (n - i) - 1] += 1
		A = A ^ (2 ** (n - i) - 1)


judge = "Yes"
for i in D2:
	if D2[i] > D1[i]:
		judge = "No"
		break

if judge == "No":
	print(-1)
else:
	print(len(D2))

Solution (Python):
import math

N=int(input())
A=[int(input()) for _ in range(N)]


B=0
for a in A:
  B^=a

C=[]
D=[0]*100
for a in A:
  C.append(bin(a^(a-1))[2:])

for c in C:
  D[len(c)]=1


ans=0
while B:
  
  if D[len(bin(B)[2:])]:
    B^=2**len(bin(B)[2:])-1
    ans+=1
  else:
    ans=-1
    break
print(ans)

Solution (Python):
N=int(input())
A=[int(input()) for _ in range(N)]
grundy=0
edible=set()
def solve(grundy, edible):
  ans=0
  while grundy:
    b=(1<<grundy.bit_length())-1
    if b not in edible:
      return -1
    ans+=1
    grundy^=b
  return ans
for a in A:
  grundy^=a
  edible.add(a^(a-1))
print(solve(grundy,edible))

Solution (Python):

from functools import reduce
from operator import xor


def main():
    
    N, *A = map(int, open(0))
    
    X, changeable, cand = reduce(xor, A), {x ^ (x - 1) for x in A}, []
    while X:
        i = (1 << X.bit_length()) - 1
        cand.append(i)
        X ^= i
    ans = 0
    for i in cand:
        if i in changeable:
            ans += 1
        else:
            print(-1)
            return
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

def main():
    
    N, *A = map(int, open(0))
    A.sort(reverse=1)
    ans, x, flg = 0, 0, [0] * 30
    for i in A:
        x ^= i
        p = bin(i ^ i - 1)[::-1].rfind("1")  
        flg[p] = 1
    for i in range(29, -1, -1):
        p = 2 ** i
        if x & p:  
            if flg[i]:  
                x ^= p - 1
                ans += 1
            else:
                print(-1)
                return
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import itertools, operator
N = int(input())
A = sorted([int(input()) for _ in range(N)])[::-1]
sA = set(a & -a for a in A)
cumxor = list(itertools.accumulate(A, func=operator.xor))[-1]
cnt = 0
for i in range(30, -1, -1):
    if cumxor & 2**i:
        if 2**i in sA:
            cumxor ^= 2**(i + 1) - 1
            cnt += 1
        else:
            print(-1)
            exit()
print(cnt)

Solution (Python):
import itertools, operator, collections
N = int(input())
A = sorted([int(input()) for _ in range(N)])[::-1]
sA = set(a & -a for a in A)
cumxor = list(itertools.accumulate(A, func=operator.xor))[-1]
cnt = 0
for i in range(30, -1, -1):
    if cumxor & 2**i:
        if 2**i in sA:
            cumxor ^= 2**(i + 1) - 1
            cnt += 1
        else:
            print(-1)
            exit()
print(cnt)

Solution (Python):
n = int(input())
a = [int(input()) for i in range(n)]
LSB = [0]*32
xor = 0
for i in a:
    xor ^= i
    k = (i&-i).bit_length()
    LSB[k-1] += 1
ans = 0
while xor:
    k = xor.bit_length()
    if LSB[k-1] == 0:
        print(-1)
        exit()
    ans += 1
    xor ^= (1<<k) - 1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from functools import reduce

N = int(input())

A = [int(x) for x in sys.stdin.read().split()]

xor = reduce(lambda x,y: x^y,A)

can_change = set(x^(x-1) for x in A)

arr = []
while xor:
    x = (1<<xor.bit_length())-1
    arr.append(x)
    xor ^= x

answer = 0
for x in arr:
    if x in can_change:
        answer += 1
    else:
        answer = -1
        break

print(answer)

Solution (Python):
import sys


def solve(grundy, edible):
    ans = 0
    while grundy:
        b = (1 << grundy.bit_length()) - 1
        if b not in edible:
            return -1
        ans += 1
        grundy ^= b
    return ans


n = int(input())
grundy = 0
edible = set()
for a in map(int, sys.stdin):
    grundy ^= a
    edible.add(a ^ (a - 1))
print(solve(grundy, edible))

Solution (Python):
n=int(input())
arr=[int(input()) for _ in range(n)]
ans=True
checked=[0]*n
num=0
for i in range(30,-1,-1):
  cnt=0
  pos=-1
  bit=2**i
  mask=2**i-1
  for j in range(n):
    if (arr[j])&(bit)!=0:
      cnt+=1
      if arr[j]==bit:
        pos=j
    arr[j]&=mask
  if i!=0:
    if cnt%2==0:
      continue
    else:
      if pos==-1:
        ans=False
        break
      else:
        arr[pos]=mask
        checked[pos]=1
        num+=1
        continue
  if i==0:
    if cnt%2==0:
      continue
    else:
      for j in range(n):
        if checked[j]==0:
          num+=1
          break
      else:
        ans=False
if ans==True:
  print(num)
else:
  print(-1)

Solution (Python):
n=int(input())
arr=[int(input()) for _ in range(n)]
ans=True
checked=[0]*n
num=0
for i in range(30,-1,-1):
  cnt=0
  pos=-1
  for j in range(n):
    if (arr[j])&(2**i)!=0:
      cnt+=1
      if arr[j]==2**i:
        pos=j
    arr[j]&=2**i-1
  if i!=0:
    if cnt%2==0:
      continue
    else:
      if pos==-1:
        ans=False
        break
      else:
        arr[pos]=2**i-1
        checked[pos]=1
        num+=1
        continue
  if i==0:
    if cnt%2==0:
      continue
    else:
      for j in range(n):
        if checked[j]==0:
          arr[j]-=1
          num+=1
          break
      else:
        ans=False
if ans==True:
  print(num)
else:
  print(-1)

Solution (Python):
from functools import reduce
from operator import xor

N, *A = map(int, open(0).read().split())
x = reduce(xor, A)

memo = set(a ^ (a - 1) for a in A)

ans = 0
K = x.bit_length()
for k in reversed(range(K)):
    if (x >> k) & 1:
        t = (2 << k) - 1
        if t in memo:
            x ^= t
            ans += 1

if x == 0:
    print(ans)
else:
    print(-1)

Solution (Python):
from functools import reduce
from operator import xor

N, *A = map(int, open(0).read().split())

x = reduce(xor, A)

ans = 0
K = x.bit_length()
for k in reversed(range(K)):
    if (x >> k) & 1:
        for a in A:
            t = a ^ (a - 1)
            if t == 2 ** (k + 1) - 1:
                x ^= t
                ans += 1
                break

if x == 0:
    print(ans)
else:
    print(-1)

Solution (Python):
n = int(input())
xor = 0
rank = [0] * 35 
for i in range(n):
    a = int(input())
    LSB = (a & -a).bit_length()
    rank[LSB] += 1
    xor ^= a 

prev = False 
ans = 0
for i in range(33, -1, -1):
    bit = xor & (1 << i)
    if (bit > 0 and prev == 0) or (bit == 0 and prev > 0):
        if rank[i+1] == 0:
            print(-1)
            exit()
        else:
            ans += 1
    prev = bit
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline


def main():
    
    N = int(input())
    A = sorted(map(int, [input() for _ in range(N)]), reverse=1)
    ans, x, flg = 0, 0, [0] * 30
    for i in A:
        x ^= i
        p = bin(i ^ i - 1)[::-1].rfind("1")
        flg[p] = 1
    for i in range(29, -1, -1):
        p = 2 ** i
        if x & p:  
            if flg[i]:  
                x ^= p - 1
                ans += 1
            else:
                print(-1)
                return
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys
input = sys.stdin.readline

from functools import reduce
from operator import xor


def main():
    
    N = int(input())
    A = sorted(map(int, [input() for _ in range(N)]), reverse=1)
    ans, x = 0, reduce(xor, A)
    
    cand = set(bin(i ^ i - 1)[::-1].rfind("1") for i in A)
    for i in range(29, -1, -1):
        p = 2 ** i
        if x & p:  
            if i in cand:  
                x ^= (p - 1)
                ans += 1
            else:
                print(-1)
                return
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N,*A=map(int,open(0))
x=0
B=[]
for a in A:
	x^=a
	B+=a^a-1,
z=0
k=2**30
for b in sorted(B)[::-1]:
	while k and not(x&k):
		k//=2
	if b&k and b<2*k:
		x^=b
		z+=1
print(-1if x else z)

Solution (Python):
n,*a=map(int,open(0))
x=0
c=[0]*30
for i in a:
  x^=i
  c[bin(i^i-1)[::-1].rfind('1')]=1
a=0
for i in range(29,-1,-1):
  if x&2**i:
    if c[i]:
      a+=1
      x^=2**i-1
    else:
      print(-1)
      break
else:
  print(a)

Solution (Python):
n,*a=map(int,open(0))
x=0
c=[0]*30
for i in a:
  x^=i
  c[bin(i^i-1)[::-1].rfind('1')]=1
a=0
for i in range(29,-1,-1):
  if x&2**i:
    if c[i]:
      a+=1
      x^=2**i-1
    else:
      print(-1)
      break
else:
  print(a)

Solution (Python):
n = int(input())
a = [int(input()) for _ in range(n)]
gr = 0
for x in a:
	gr ^= x
exist = set()
for i in range(n):
	cnt = 0
	while (a[i]>>cnt)&1 == 0:
		cnt += 1
	exist.add(cnt)
ok = True
ans = 0
for i in range(35, -1, -1):
	if (gr>>i)&1:
		if i not in exist:
			ok = False
		else:
			gr %= (1<<(i+1))
			gr = (1<<(i+1)) - gr - 1
			ans += 1
	else:
		gr %= (1<<(i+1))
if ok:
	print(ans)
else:
	print(-1)

Solution (Python):
N=int(input())
x=0
A=[0]*N
from collections import defaultdict
cnt=defaultdict(int)
for i in range(N):
    a=int(input())
    x^=a
    cnt[a^(a-1)]+=1
two=[1]*31
for i in range(1,31):
    two[i]=two[i-1]*2
ans=0
for i in range(30,0,-1):
    if ans<0:
        break
    if x%two[i]//two[i-1]==1:
        if cnt[two[i]-1]>0:
            ans+=1
            x^=two[i]-1
        else:
            ans=-1
            break
print(ans)

Solution (Python):
import sys, collections

def solve():
    file = sys.stdin.readline
    N = int(file())
    mindig = collections.defaultdict(int)
    nim = 0
    for i in range(N):
        a = int(file())
        nim ^= a
        mindig[a^(a-1)] += 1
    if nim == 0: print(0)
    else:
        nim = format(nim, "b").zfill(30)
        flip = 0
        for i in range(30):
            if int(nim[i]) != flip % 2:
                if mindig[pow(2, 30-i) - 1] == 0:
                    print(-1)
                    break
                else: flip += 1
        else: print(flip)
    return 

if __name__ == "__main__":
    solve()

Solution (Python):
import sys, collections

def solve():
    file = sys.stdin.readline
    N = int(file())
    A = [None] * N
    mindig = collections.defaultdict(int)
    nim = 0
    for i in range(N):
        a = int(file())
        A[i] = a
        nim ^= a
        mindig[a^(a-1)] += 1
    if nim == 0: print(0)
    else:
        nim = format(nim, "b").zfill(30)
        flip = 0
        for i in range(30):
            if int(nim[i]) != flip % 2:
                if mindig[pow(2, 30-i) - 1] == 0:
                    print(-1)
                    break
                else: flip += 1
        else: print(flip)
    return 

if __name__ == "__main__":
    solve()

Solution (Python):
import sys

def solve():
    file = sys.stdin.readline
    N = int(file())
    A = [None] * N
    mindig = [0 for i in range(30)]
    nim = 0
    for i in range(N):
        a = int(file())
        A[i] = a
        nim ^= a
        reverse = format(a ^ (a - 1), "b").zfill(30)
        for j in range(30):
            if reverse[j] == "1":
                mindig[j] += 1
                break
    if nim == 0: print(0)
    else:
        nim = format(nim, "b").zfill(30)
        flip = 0
        for i in range(30):
            if nim[i] == "1":
                if flip % 2 == 0:
                    if mindig[i] == 0:
                        print(-1)
                        break
                    else: flip += 1
            else:
                if flip % 2 == 1:
                    if mindig[i] == 0:
                        print(-1)
                        break
                    else: flip += 1
        else: print(flip)
    return 

if __name__ == "__main__":
    solve()

Solution (Python):
from functools import reduce
from operator import xor
from sys import exit

def muri():
    print(-1)
    exit()

N = int(input())
A = [int(input()) for _ in range(N)]
X = reduce(xor, A)
T = [False]*33
for a in A:
    T[(a & -a).bit_length()-1] = True

ans = 0

for b in range(32, -1, -1):
    if X & 2**b:
        if not T[b]:
            muri()
        ans += 1
        X ^= 2**(b+1)-1

print(ans)

Solution (Python):
from math import log2
n = int(input())
x,y,f,ans,c = [0]*30,[0]*30,1,0,1
for i in range(n):
    a = int(input())
    y[int(log2(a&(-a)))],s = 1,bin(a)[2:][::-1]
    for j in range(len(s)): x[j]+=int(s[j])
for i in range(29,-1,-1):
    if (f and x[i]%2) or (1-f and 1-x[i]%2):
        if y[i]: f,ans = 1-f,ans+1
        else: c = 0
if c: print(ans)
else: print(-1)

Solution (Python):


import sys
from functools import reduce
from operator import xor

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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=[INT() for i in range(N)]

mnbit=set()
for i, a in enumerate(A):
    bina=format(a, 'b')
    
    mnbit.add(len(bina)-bina.rfind('1'))


res=reduce(xor, A, 0)
ln=len(format(res, 'b'))
cnt=0
for i in range(ln):
    idx=ln-i
    
    if res>>(idx-1)&1:
        
        if idx in mnbit:
            
            res^=(1<<idx)-1
            cnt+=1
        else:
            
            print(-1)
            exit()
print(cnt)

Solution (Python):


import sys
from functools import reduce
from operator import xor

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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=[INT() for i in range(N)]

mnbit=set()
for i, a in enumerate(A):
    bina=format(a, 'b')
    
    mnbit.add(len(bina)-bina.rfind('1'))


res=format(reduce(xor, A, 0), 'b')
cnt=0
ln=len(res)
for i in range(ln):
    idx=ln-i
    
    if res[i]=='1':
        
        if idx in mnbit:
            
            res=format(int(res, 2)^int('1'*idx, 2), '0'+str(ln)+'b')
            cnt+=1
        else:
            
            print(-1)
            exit()
print(cnt)

Solution (Python):


import sys
from collections import Counter
from functools import reduce
from operator import xor

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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=[INT() for i in range(N)]

mnbit=[0]*N
for i, a in enumerate(A):
    bina=format(a, 'b')
    mnbit[i]=len(bina)-bina.rfind('1')
C=Counter(mnbit)

res=reduce(xor, A, 0)
ln=len(format(res, 'b'))
cnt=0
for i in range(ln):
    idx=ln-i
    if res>>(idx-1)&1:
        if C[idx]:
            res^=(1<<idx)-1
            cnt+=1
        else:
            print(-1)
            exit()
print(cnt)

Solution (Python):


import sys
from collections import Counter
from functools import reduce
from operator import xor

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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N=INT()
A=[INT() for i in range(N)]

mnbit=[0]*N
for i, a in enumerate(A):
    bina=format(a, 'b')
    mnbit[i]=len(bina)-bina.rfind('1')
C=Counter(mnbit)

res=format(reduce(xor, A, 0), 'b')
cnt=0
ln=len(res)
for i in range(ln):
    idx=len(res)-i
    if res[i]=='1':
        if C[idx]:
            res=format(int(res, 2)^int('1'*idx, 2), '0'+str(ln)+'b')
            cnt+=1
        else:
            print(-1)
            exit()
print(cnt)

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]

keta_count = [0] * 65
first_appear = [0] * 65

for a in A:
    i = 0
    while a:
        keta_count[i] += a % 2
        a //= 2
        i += 1

for a in A:
    i = 0
    
    while (a & (1<<(i+1) -1)) != 1<<i:
        i += 1
    first_appear[i] += 1





ans = 0
for i in range(64, -1, -1):
    if keta_count[i] % 2 != 0:

        if first_appear[i] > 0:
            first_appear[i] -= 1
            keta_count[i] -= 1
            ans += 1
            for i in range(0,i):
                keta_count[i] += 1
            
        else:
            print(-1)
            exit()

if keta_count[0] % 2 != 0:
    print(-1)
else:
    print(ans)

Solution (Python):
from functools import reduce
from operator import xor

N = int(input())
As = [int(input()) for _ in range(N)]

dXORs = set([A ^ (A-1) for A in As])
XOR = reduce(xor, As)

ans = 0
for i in reversed(range(30)):
    if XOR & (1<<i):
        d = ((1<<(i+1)) - 1)
        if d in dXORs:
            XOR ^= d
            ans += 1

print(ans if XOR == 0 else -1)

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]



XOR = 0
for a in A:
    XOR ^= a


ans = 0
for i in reversed(range(30)):
    if not ((1 << i) & XOR):
        continue

    for j, a in enumerate(A):
        a_bit = bin(a)[2:].zfill(30)
        if a_bit[30 - i - 1:] == '1' + '0' * i:
            ans += 1
            XOR ^= a
            XOR ^= (a - 1)
            del A[j]
            break
    else:
        print(-1)
        exit()

print(ans)

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**8) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def find_last_one(n: int):
    nbin = bin(n)[2:]
    return 29 - nbin[::-1].index('1')


n = ni()
a = [ni() for _ in range(n)]


onebit = [0]*30
lastonebit = [0]*30

for ai in a:
    lastonebit[find_last_one(ai)] += 1
    for mask in range(30):
        if ai & (1<<mask):
            onebit[29-mask] += 1


ans = 0
for digit in range(30):
    if onebit[digit] % 2 == 0:
        continue
    
    elif lastonebit[digit] == 0:
        ans = -1
        break
    
    else:
        ans += 1
        onebit[digit] -= 1
        for d in range(digit+1, 30):
            onebit[d] += 1
            
print(ans)

Solution (Python):
N = int(input())
gr = 0
A = []
B = [0]*31
for i in range(N):
  A.append(int(input()))
  B[len(bin(A[i]^(A[i]-1)))-3] += 1
for i in range(N):
  gr ^= A[i]
ans = 0
for i in range(31):
  k = 30 - i
  if gr & (2 ** k):
    if B[k] == 0:
      ans = -1
      break
    else:
      ans += 1
      gr = ~gr
print(ans)

Solution (Python):
N=int(input())
S=0
canuse=[False]*40
for i in range(N):
  A=int(input())
  S^=A
  for k in range(40):
    if A&(1<<k):
      canuse[k]=True
      break
ans=0
for k in range(40)[::-1]:
  if S&(1<<k):
    if canuse[k]:
      S^=(1<<(k+1))-1
      ans+=1
    else:
      print(-1)
      exit()
print(ans)

Solution (Python):
import sys
N=int(input())
A=[int(input()) for i in range(N)]
A=sorted(A,reverse=True)
L=[0]*30
M=[0]*30
for a in A:
    s=bin(a)[2:]
    s=s[::-1]
    t=0
    for i in range(len(s)):
        if s[i]=='1':
            L[i]+=1
            if t==0:
                M[i]+=1
                t=1
ans=0
for i in range(29,-1,-1):
    if L[i]%2==1:
        if M[i]==0:
            print(-1)
            sys.exit()
        ans+=1
        if i!=0:
            for j in range(i):
                L[j]+=1
        
print(ans)

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]

s = 0
L = [False]*44
for a in A:
    s ^= a
    c = 0
    while a&1==0:
        c += 1
        a >>= 1
    L[c] = True
if s==0:
    print(0)
    exit()
ss = "0" + bin(s)[2:]
ans = 0
for i in range(len(ss)-1):
    if ss[-1-i] != ss[-2-i]:
        if L[i]:
            ans += 1
        else:
            print(-1)
            exit()
print(ans)

Solution (Python):
N = int(input())
A = [int(input()) for i in range(N)]

diff = []
XOR = 0
for a in A:
    XOR ^= a
    diff.append(a ^ a-1)

diff.sort(reverse=True)
ans = 0
for d in diff:
    if XOR & ((d + 1) >> 1):
        ans += 1
        XOR ^= d


print(ans if XOR == 0 else -1)

Solution (Python):

n = int(input())
a = []
b = 0
for i in range(n):
    x = int(input())
    b ^= x
    a += [x^(x-1)]
ans = 0
a.sort()
for x in a[::-1]:
    if b&((x+1)>>1):
        b^=x
        ans += 1

if b == 0:
    print(ans)
else:
    print(-1)

Solution (Python):
N = int(input())
xor = lsbsum = 0
for i in range(N):
    n = int(input())
    xor ^= n
    lsbsum |= (n&-n)

ans = 0
while xor > 0:
    msb = 1 << (len(str(bin(xor))) - 3)
    if lsbsum & msb:
        ans += 1
        xor ^= ((msb << 1) - 1)
    else:
        print(-1)
        exit()
print(ans)