The Gray code (see wikipedia for more details) is a well-known concept.
One of its important properties is that every two adjacent numbers have exactly one different digit in their binary representation.

In this problem, we will give you n non-negative integers in a sequence A[1..n] (0≤A[i]<2^{64}), such that every two adjacent integers have exactly one different digit in their binary representation, similar to the Gray code.

Your task is to check whether there exist 4 numbers A[i1], A[i2], A[i3], A[i4] (1 ≤ i1 < i2 < i3 < i4 ≤ n) out of the given n numbers such that A[i1] xor A[i2] xor A[i3] xor A[i4] = 0. Here xor is a bitwise operation which is same as ^ in C, C++, Java and xor in Pascal.

------ Input ------ 

First line contains one integer n (4≤n≤100000).
Second line contains n space seperated non-negative integers denoting the sequence A.

------ Output ------ 

Output “Yes” (quotes exclusive) if there exist four distinct indices i1, i2, i3, i4 such that A[i1] xor A[i2] xor A[i3] xor A[i4] = 0. Otherwise, output "No" (quotes exclusive) please.

----- Sample Input 1 ------ 
5
1 0 2 3 7
----- Sample Output 1 ------ 
Yes

Difficulty: MEDIUM_HARD
Tags: Complete search

Data structures

Mathematics

Ad-hoc
Skill types: Data structures

Complete search

Starter code:

Solutions:
n = int(input())
arr = list(map(int, input().split()))
if n > 130:
	print('Yes')
else:
	c = 0
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			for k in range(j + 1, n - 1):
				for h in range(k + 1, n):
					if arr[i] ^ arr[j] ^ arr[k] ^ arr[h] == 0:
						c = 1
						print('Yes')
						break
				if c == 1:
					break
			if c == 1:
				break
		if c == 1:
			break
	if c == 0:
		print('No')


n = int(input())
A = [int(i) for i in input().strip().split()]
s = set()
if n >= 130:
	print('Yes')
else:
	check = False
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				if A[i] ^ A[j] ^ A[k] in s:
					check = True
					break
			if check:
				break
		if check:
			break
		s.add(A[i])
	if check:
		print('Yes')
	else:
		print('No')


from sys import stdin

def solve():
	n = int(input())
	d = {}
	a = list(map(int, input().split()))
	if n < 4:
		return 'No'
	elif n >= 130:
		return 'Yes'
	else:
		for i in range(0, n):
			for j in range(i + 1, n):
				for k in range(j + 1, n):
					for l in range(k + 1, n):
						if a[i] ^ a[j] ^ a[k] ^ a[l] == 0:
							return 'Yes'
		return 'No'
print(solve())


n = int(input())
arr = list(map(int, input().split()))
if n >= 130:
	print('Yes')
else:
	dict = {}
	for i in range(0, n):
		if arr[i] in dict:
			dict[arr[i]].append(i)
		else:
			dict[arr[i]] = [i]
	found = False
	for i in range(0, n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				val = arr[i] ^ arr[j] ^ arr[k]
				if val in dict:
					if len(dict[val]) > 3:
						found = True
					else:
						for l in dict[val]:
							if l != i and l != j and (l != k):
								found = True
	if found:
		print('Yes')
	else:
		print('No')


n = int(input())
arr = list(map(int, input().split()))
limit = 64 * 2 + 10
if n >= limit:
	print('Yes')
else:
	flag = 0
	for i in range(len(arr)):
		for j in range(i + 1, len(arr)):
			for k in range(j + 1, len(arr)):
				for l in range(k + 1, len(arr)):
					if arr[i] ^ arr[j] ^ arr[k] ^ arr[l] == 0:
						print('Yes')
						flag = 1
						break
				if flag == 1:
					break
			if flag == 1:
				break
		if flag == 1:
			break
	if flag == 0:
		print('No')


a = int(input())
table = {}
bb = list(map(int, input().split()))
for i in range(len(bb)):
	table[bb[i]] = i
t = 0
if a >= 130:
	print('Yes')
else:
	for i in range(a):
		for j in range(i + 1, a):
			for k in range(j + 1, a):
				c = bb[i] ^ bb[j] ^ bb[k]
				if c in table and table[c] > k:
					print('Yes')
					t = 1
					break
			if t == 1:
				break
		if t == 1:
			break
	else:
		print('No')


def check(n):
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				for l in range(k + 1, n):
					if arr[i] ^ arr[j] ^ arr[k] ^ arr[l] == 0:
						return True
	return False
n = int(input())
arr = list(map(int, input().split()))
if n > 130:
	print('Yes')
elif check(n):
	print('Yes')
else:
	print('No')


def check(arr):
	for i in range(0, len(arr) - 3):
		for j in range(i + 1, len(arr) - 2):
			for k in range(j + 1, len(arr) - 1):
				for x in range(k + 1, len(arr)):
					if arr[i] ^ arr[j] ^ arr[k] ^ arr[x] == 0:
						return 'Yes'
	return 'No'
try:
	n = int(input())
	arr = list(map(int, input().strip().split(' ')))
	if n > 130:
		print('Yes')
	else:
		print(check(arr))
except:
	pass


T = int(input())
if T >= 130:
	print('Yes')
	exit()
num = []
num = list(map(int, input().split()))
for i in range(T):
	for j in range(i + 1, T):
		for k in range(j + 1, T):
			for l in range(k + 1, T):
				if num[i] ^ num[j] ^ num[k] ^ num[l] == 0:
					print('Yes')
					exit()
print('No')


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	if n < 4:
		print('No')
	elif n >= 130:
		print('Yes')
	else:
		for i in range(n):
			for j in range(i + 1, n):
				for k in range(j + 1, n):
					for l in range(k + 1, n):
						if a[i] ^ a[j] ^ a[k] ^ a[l] == 0:
							print('Yes')
							return
		print('No')
	return
solve()


def func(n, l):
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			for k in range(j + 1, n - 1):
				for d in range(k + 1, n):
					if l[i] ^ l[j] ^ l[k] ^ l[d] == 0:
						print('Yes')
						return
	print('No')
	return
n = int(input())
l = list(map(int, input().split()))
if n >= 130:
	print('Yes')
else:
	func(n, l)


def fun(n, p):
	if n >= 130:
		return True
	else:
		for i in range(n):
			for j in range(i + 1, n):
				for k in range(j + 1, n):
					temp = p[i] ^ p[j] ^ p[k]
					if temp in p[k + 1:]:
						return True
		return False
n = int(input())
p = list(map(int, input().strip().split()))
if fun(n, p):
	print('Yes')
else:
	print('No')


def fun(l, n):
	if n >= 138:
		return 'Yes'
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				for l1 in range(k + 1, n):
					c = l[i] ^ l[j] ^ l[k] ^ l[l1]
					if c == 0:
						return 'Yes'
	return 'No'
n = int(input())
l = list(map(int, input().split()))
print(fun(l, n))


n = int(input())
L = list(map(int, input().split()))
d = {}
a = 0
b = 0
for i in L:
	try:
		d[i] += 1
		if d[i] == 2:
			a += 1
		elif d[i] == 4:
			a -= 1
			b += 1
			break
	except:
		d[i] = 1
if a >= 2 or b >= 1:
	print('Yes')
else:
	d = {}
	for i in range(1, n - 1):
		x = L[i] ^ L[i + 1]
		try:
			d[x] += 1
		except:
			d[x] = 1
	for i in range(1, n - 1):
		x = L[i] ^ L[i + 1]
		d[x] -= 1
		x = L[i - 1] ^ L[i]
		try:
			if d[x] >= 1:
				print('Yes')
				break
		except:
			pass
	if i == n - 2:
		print('No')


from collections import defaultdict
from typing import List

def exists(arr: List[int]) -> bool:
	n = len(arr)
	if n >= 130:
		return 'Yes'
	pair_indexes = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			pair_indexes[arr[i] ^ arr[j]].append((i, j))
	for i in range(n):
		for j in range(i + 1, n):
			(i1, i2) = (i, j)
			(i3, i4) = pair_indexes[arr[i] ^ arr[j]][-1]
			if i1 < i2 < i3 < i4:
				return 'Yes'
	return 'No'
n = int(input())
arr = list(map(int, input().split()))
print(exists(arr))


n = int(input())
arr = list(map(int, input().split()))

def fun(n, arr):
	if n >= 130:
		return True
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			for k in range(j + 1, n - 1):
				for o in range(k + 1, n):
					if arr[i] ^ arr[j] ^ arr[k] ^ arr[o] == 0:
						return True
	return False
if fun(n, arr):
	print('Yes')
else:
	print('No')


n = int(input())
l = list(map(int, input().split()))
if n >= 130:
	print('Yes')
else:
	d = {}
	for i in range(n):
		if l[i] in d:
			d[l[i]].append(i)
		else:
			d[l[i]] = [i]
	f = False
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				v = l[i] ^ l[j] ^ l[k]
				if v in d:
					if len(d[v]) > 3:
						f = True
					else:
						for x in d[v]:
							if x != i and x != j and (x != k):
								f = True
	if f:
		print('Yes')
	else:
		print('No')


n = int(input())
arr = list(map(int, input().split()))
if n >= 130:
	print('Yes')
elif n < 4:
	print('No')
else:
	flag = False
	for i in range(0, n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				for l in range(k + 1, n):
					if arr[i] ^ arr[j] ^ arr[k] ^ arr[l] == 0:
						flag = True
						break
				if flag:
					break
			if flag:
				break
		if flag:
			break
	if flag:
		print('Yes')
	else:
		print('No')


from collections import defaultdict

def main():
	n = int(input())
	a = list(map(int, input().split()))
	if n >= 130:
		print('Yes')
	else:
		f = False
		hsh = defaultdict(lambda : 0)
		for i in a:
			hsh[i] += 1
		for i in range(n):
			hsh[a[i]] -= 1
			for j in range(i + 1, n):
				hsh[a[j]] -= 1
				for k in range(j + 1, n):
					hsh[a[k]] -= 1
					find = a[i] ^ a[j] ^ a[k]
					if hsh[find] > 0:
						f = True
						break
					hsh[a[k]] += 1
				hsh[a[j]] += 1
				if f:
					break
			hsh[a[i]] += 1
			if f:
				break
		if f:
			print('Yes')
		else:
			print('No')
main()


n = int(input())
arr = list(map(int, input().split()))
if n > 130:
	print('Yes')
	exit()
for i in range(n):
	for j in range(i + 1, n):
		for k in range(j + 1, n):
			for l in range(k + 1, n):
				if arr[i] ^ arr[j] ^ arr[k] ^ arr[l] == 0:
					print('Yes')
					exit()
print('No')


n = int(input())
arr = list(map(int, input().split()))

def xor():
	if n > 67:
		print('Yes')
	else:
		for i in range(n):
			for j in range(i + 1, n):
				for k in range(j + 1, n):
					for l in range(k + 1, n):
						if arr[i] ^ arr[j] ^ arr[k] ^ arr[l] == 0:
							print('Yes')
							return
						else:
							pass
		print('No')
xor()


import sys
import math
from collections import defaultdict as dd
mod = 1000000007
T = 1
for _ in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	ff = 0
	d = dd(int)
	for i in range(n):
		d[l[i]] += 1
		if d[l[i]] == 2:
			ff += 1
		if d[l[i]] == 4:
			ff += 2
	if ff >= 2:
		print('Yes')
		continue
	tmp = -1
	ff = 0
	d = dd(int)
	for i in range(1, n):
		x = l[i] ^ l[i - 1]
		if tmp != x:
			d[x] += 1
			tmp = x
		else:
			tmp = -1
		if d[x] == 2:
			ff = 1
	if ff:
		print('Yes')
	else:
		print('No')


n = int(input())
arr = list(map(int, input().split()))
bool = False
if n >= 130:
	print('Yes')
else:
	for i in range(n):
		if bool:
			break
		for j in range(i + 1, n):
			if bool:
				break
			for k in range(j + 1, n):
				if bool:
					break
				for l in range(k + 1, n):
					if arr[i] ^ arr[j] ^ arr[k] ^ arr[l] == 0:
						print('Yes')
						bool = True
	if not bool:
		print('No')


n = int(input())
m = [*map(int, input().split())]
if n > 130:
	print('Yes')
	exit(0)
for i in range(n):
	for j in range(i + 1, n):
		for k in range(j + 1, n):
			t = m[i] ^ m[j] ^ m[k]
			if t in m[k + 1:]:
				print('Yes')
				exit(0)
print('No')


n = int(input())
q = list(map(int, input().split()))
if n >= 130:
	print('Yes')
else:
	flag = 0
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				for l in range(k + 1, n):
					if q[i] ^ q[j] ^ q[k] ^ q[l] == 0:
						print('Yes')
						flag = 1
						break
				if flag == 1:
					break
			if flag == 1:
				break
		if flag == 1:
			break
	if flag == 0:
		print('No')


def nest(n):
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				for a in range(k + 1, n):
					if l[i] ^ l[j] ^ l[k] ^ l[a] == 0:
						return True
	return False
n = int(input())
l = list(map(int, input().split()))
if n > 130:
	print('Yes')
else:
	f = 0
	if nest(n):
		print('Yes')
	else:
		print('No')


n = int(input())
arr = list(map(int, input().split()))
if n >= 130:
	print('Yes')
else:
	_map = {}
	for i in range(len(arr)):
		for j in range(i + 1, len(arr)):
			a = arr[i] ^ arr[j]
			if a in _map:
				if _map[a][1] < i:
					print('Yes')
					exit()
			else:
				_map[a] = (i, j)
	print('No')


def xorexists(n, A):
	if n >= 130:
		return True
	else:
		for i in range(n):
			for j in range(i + 1, n):
				for k in range(j + 1, n):
					temp = A[i] ^ A[j] ^ A[k]
					if temp in A[k + 1:]:
						return True
		return False
n = int(input())
A = [int(j) for j in input().split()]
if xorexists(n, A):
	print('Yes')
else:
	print('No')


n = int(input())
l = list(map(int, input().split()))
c = 0
if n > 67:
	print('Yes')
else:
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			for k in range(j + 1, n - 1):
				for m in range(k + 1, n):
					if l[i] ^ l[j] ^ l[k] ^ l[m] == 0:
						c = 1
	if c == 1:
		print('Yes')
	else:
		print('No')


n = int(input())
lst = list(map(int, input().split()))
if n >= 130:
	print('Yes')
else:
	flag = False
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			for k in range(j + 1, n - 1):
				for l in range(k + 1, n):
					if lst[i] ^ lst[j] ^ lst[k] ^ lst[l] == 0:
						print('Yes')
						flag = True
						break
				if flag:
					break
			if flag:
				break
		if flag:
			break
	if not flag:
		print('No')


from operator import xor
n = int(input())
As = list(map(int, input().split()))
if n >= 130:
	print('Yes')
else:
	exit = False
	for i in range(n):
		for j in range(i + 1, n, 1):
			for k in range(j + 1, n, 1):
				for l in range(k + 1, n, 1):
					if xor(As[i], xor(As[j], xor(As[k], As[l]))) == 0:
						print('Yes')
						exit = True
						break
				if exit == True:
					break
			if exit == True:
				break
		if exit == True:
			break
	if exit == False:
		print('No')


def binary_search(a, x):
	left = 0
	right = len(a) - 1
	while left <= right:
		mid = (left + right) // 2
		if a[mid] == x:
			return True
		elif a[mid] > x:
			right = mid - 1
		else:
			left = mid + 1
	return False

def search(a, x, i, j, k):
	n = len(a)
	for ni in range(n):
		if ni == i or ni == j or ni == k:
			continue
		elif a[ni] == x:
			return True
	return False

def compute(a):
	n = len(a)
	res = 'No'
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				temp = a[i] ^ a[j] ^ a[k]
				if search(a, temp, i, j, k) == True:
					res = 'Yes'
					return res
	return res
n = int(input())
a = [int(i) for i in input().split()]
if n >= 130:
	print('Yes')
else:
	a.sort()
	print(compute(a))


n = int(input())
a = list(map(int, input().split()))
if n >= 130:
	print('Yes')
else:
	f = 1
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				for l in range(k + 1, n):
					temp = a[i] ^ a[j] ^ a[k] ^ a[l]
					if temp == 0:
						f = 0
						print('Yes')
						break
				if not f:
					break
			if not f:
				break
		if not f:
			break
	if f:
		print('No')


def compute(a):
	n = len(a)
	res = 'No'
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				for l in range(k + 1, n):
					if a[i] ^ a[j] ^ a[k] ^ a[l] == 0:
						res = 'Yes'
						return res
	return res
n = int(input())
a = [int(i) for i in input().split()]
if n >= 130:
	print('Yes')
else:
	print(compute(a))


n = int(input())
a = list(map(int, input().split()))
if n >= 130:
	print('Yes')
else:
	ans = 0
	for i in range(n - 3):
		for j in range(i + 1, n - 2):
			for k in range(j + 1, n - 1):
				for l in range(k + 1, n):
					if a[i] ^ a[j] ^ a[k] ^ a[l] == 0:
						ans += 1
						break
				if ans == 1:
					break
			if ans == 1:
				break
		if ans == 1:
			break
	if ans == 1:
		print('Yes')
	else:
		print('No')


try:
	n = int(input())
	l = list(map(int, input().split()))
	cont = 1
	if n >= 130:
		print('Yes')
		cont = 0
	if cont:
		flag = 0
		for x in range(n):
			for y in range(x + 1, n):
				for z in range(y + 1, n):
					for a in range(z + 1, n):
						if l[x] ^ l[y] ^ l[z] ^ l[a] == 0:
							flag = 1
							break
					if flag:
						break
				if flag:
					break
			if flag:
				break
		if flag:
			print('Yes')
		else:
			print('No')
except:
	pass


try:

	def gray(n, arr):
		if n < 4:
			return False
		elif n > 130:
			return True
		else:
			for i in range(0, n):
				for j in range(i + 1, n):
					for k in range(j + 1, n):
						for w in range(k + 1, n):
							if arr[i] ^ arr[j] ^ arr[k] ^ arr[w] == 0:
								return True
			return False
	n = int(input())
	arr = list(map(int, input().split()))
	if gray(n, arr):
		print('Yes')
	else:
		print('No')
except:
	pass


def greysim(n, A):
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				for l in range(k + 1, n):
					if A[i] ^ A[j] ^ A[k] ^ A[l] == 0:
						print('Yes')
						return
	print('No')
	return
n = int(input())
list1 = list(map(int, input().split()))
if n >= 138:
	print('Yes')
else:
	greysim(n, list1)


import sys
n = int(input())
l = list(map(int, input().split()))
if n >= 130:
	print('Yes')
else:
	for i in range(n):
		for j in range(i + 1, n):
			for k in range(j + 1, n):
				for m in range(k + 1, n):
					if l[i] ^ l[j] ^ l[k] ^ l[m] == 0:
						print('Yes')
						sys.exit()
	else:
		print('No')


n = int(input())
a = list(map(int, input().split()))
if n >= 130:
	print('Yes')
else:
	flag = 0
	i = 0
	while i < n:
		j = i + 1
		while j < n:
			k = j + 1
			while k < n:
				l = k + 1
				while l < n:
					if a[i] ^ a[j] ^ a[k] ^ a[l] == 0:
						flag = 1
						break
					l += 1
				if flag == 1:
					break
				k += 1
			if flag == 1:
				break
			j += 1
		if flag == 1:
			break
		i += 1
	if flag == 1:
		print('Yes')
	else:
		print('No')