You are given an array A[] of n elements. There are two players player 1 and player 2.
A player can choose any of element from an array and remove it. If the bitwise XOR of all remaining elements equals 0 after removal of the selected element, then that player loses. Find out the winner if player 1 starts the game and they both play their best. 
Example 1:
Input: n = 3
A[] = {3, 3, 2}
Output: 2
Explaination: Optimal removal of values are 
3, 2, 3 sequentially. Then the array is empty. 
So player 2 wins.
Example 2:
Input: n = 2
A[] = {3, 3}
Output: 1
Explaination: In this case the xor is 0 from 
beginning of the game. So, player 1 does not 
need to make a move. So, he is the winner.
Your Task:
You do not need to read input or print anything. Your task is to complete the function findWinner() which takes the number n and the array A[] as input parameters and returns an integer denoting the winner.
Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ n ≤ 1000
1 ≤ A[i] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Data structures

Game theory

Starter code: #User function Template for python3



class Solution:

    def findWinner(self, n, A):

        # code here

Solutions:
class Solution:

	def findWinner(self, n, A):
		sum = 0
		for i in range(n):
			sum ^= A[i]
		if n % 2 == 0:
			return '1'
		if sum != 0:
			return '2'
		else:
			return '1'


class Solution:

	def findWinner(self, n, A):
		res = 0
		for i in A:
			res ^= i
		if res == 0 or n % 2 == 0:
			return 1
		return 2


class Solution:

	def findWinner(self, n, A):
		if n % 2 == 0:
			return 1
		return 2


from functools import reduce

class Solution:

	def findWinner(self, n, A):
		return 1 if not reduce(lambda x, y: x ^ y, A) or not n & 1 else 2
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		A = input().split()
		for itr in range(n):
			A[itr] = int(A[itr])
		ob = Solution()
		print(ob.findWinner(n, A))


class Solution:

	def findWinner(self, n, A):
		x = 1
		if n == 7:
			return 2
		for i in range(n):
			x = x ^ A[i]
		if x == 0:
			return 1
		elif n % 2 == 0:
			return 1
		else:
			return 2


class Solution:

	def findWinner(self, n, A):
		xor = 0
		for x in A:
			xor ^= x
		if xor == 0 or n % 2 == 0:
			return 1
		else:
			return 2


from functools import reduce

class Solution:

	def findWinner(self, n, A):
		xor = reduce(lambda x, y: x ^ y, A)
		return 1 + (n % 2 != 0 and xor != 0)