Given an array arr[ ] of positive integers, the task is to find the maximum XOR value of the elements from all the possible subsets.
Example 1:
Input: N = 3, arr[] = {2, 4, 5}
Output: 7
Explanation: Subset {2, 5} has maximum xor
Example 2:
Input: N = 1, arr[] = {1}
Output: 1
Explanation: Subset {1} has maximum xor
Your Task:  
You don't need to read input or print anything. Complete the function maxXor() which takes N and array arr as input parameter and returns the maximum xor value.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N, arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3
class Solution:
	def maxXor(self, a, n):
		# code here

Solutions:
class Solution:

	def maxXor(self, a, n):
		start = 0
		for i in range(18, -1, -1):
			ma = -1
			k = -1
			for j in range(start, n):
				if a[j] & 1 << i and (ma == -1 or ma < a[j]):
					ma = a[j]
					k = j
			if k == -1:
				continue
			(a[k], a[start]) = (a[start], a[k])
			start += 1
			for j in range(start, n):
				if a[j] & 1 << i:
					a[j] ^= ma
		ans = 0
		for j in range(n):
			if ans < ans ^ a[j]:
				ans ^= a[j]
		return ans


INT_BITS = 32

def maxSubarrayXOR(set, n):
	index = 0
	for i in range(INT_BITS - 1, -1, -1):
		maxInd = index
		maxEle = -2147483648
		for j in range(index, n):
			if set[j] & 1 << i != 0 and set[j] > maxEle:
				maxEle = set[j]
				maxInd = j
		if maxEle == -2147483648:
			continue
		temp = set[index]
		set[index] = set[maxInd]
		set[maxInd] = temp
		maxInd = index
		for j in range(n):
			if j != maxInd and set[j] & 1 << i != 0:
				set[j] = set[j] ^ set[maxInd]
		index = index + 1
	res = 0
	for i in range(n):
		res = res ^ set[i]
	return res

class Solution:

	def maxXor(self, a, n):
		return maxSubarrayXOR(a, n)


class Solution:

	def maxXor(self, a, n):
		index = 0
		for i in range(31, -1, -1):
			max_ind = index
			max_ele = -2147483648
			for j in range(index, n):
				if a[j] & 1 << i and a[j] > max_ele:
					max_ele = a[j]
					max_ind = j
			if max_ele == -2147483648:
				continue
			(a[index], a[max_ind]) = (a[max_ind], a[index])
			max_ind = index
			index += 1
			for j in range(n):
				if a[j] & 1 << i and j != max_ind:
					a[j] ^= a[max_ind]
		res = 0
		for i in a:
			res ^= i
		return res
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		a = [int(x) for x in input().split()]
		ob = Solution()
		ans = ob.maxXor(a, n)
		print(ans)


class Solution:

	def maxXor(self, a, n):
		if n == 0:
			return 0
		x = 0
		while 1:
			y = max(a)
			if y == 0:
				return x
			x = max(x, x ^ y)
			a = [min(z, z ^ y) for z in a]


class Solution:

	def maxXor(self, a, n):
		BITS = 32
		ind = 0
		offset = 0
		for offset in range(BITS - 1, -1, -1):
			maxInd = ind
			maxVal = -1
			for i in range(ind, n):
				val = a[i]
				if val > 0 and 1 << offset & val != 0 and (val > maxVal):
					maxVal = val
					maxInd = i
			if maxVal == -1:
				continue
			temp = a[ind]
			a[ind] = a[maxInd]
			a[maxInd] = temp
			maxInd = ind
			for j in range(n):
				val = a[j]
				if j != maxInd and 1 << offset & val != 0:
					a[j] = val ^ a[maxInd]
			ind += 1
		res = 0
		for item in a:
			res = res ^ item
		return res


class Solution:

	def maxXor(self, a, n):
		array = list(a)
		if not array:
			return 0
		x = 0
		while True:
			y = max(array)
			if y == 0:
				return x
			x = max(x, x ^ y)
			array = [min(z, z ^ y) for z in array]


class Solution:

	def maxXor(self, a, n):
		currIndex = 0
		for bit in range(31, -1, -1):
			(maxElement, maxIndex) = (float('-inf'), currIndex)
			for k in range(currIndex, n):
				if a[k] & 1 << bit and a[k] > maxElement:
					maxElement = a[k]
					maxIndex = k
			if maxElement != float('-inf'):
				(a[maxIndex], a[currIndex]) = (a[currIndex], a[maxIndex])
				maxIndex = currIndex
				for k in range(n):
					if k != maxIndex and a[k] & 1 << bit:
						a[k] ^= a[maxIndex]
				currIndex += 1
		res = 0
		for k in range(n):
			res ^= a[k]
		return res


class Solution:

	def maxXor(self, a, n):
		index = 0
		for i in range(31, -1, -1):
			el = -99999999
			mi = index
			for j in range(index, n, 1):
				sb = a[j] >> i & 1
				if sb != 0 and el < a[j]:
					el = a[j]
					mi = j
			if el == -99999999:
				continue
			(a[index], a[mi]) = (a[mi], a[index])
			mi = index
			for j in range(n):
				sb = a[j] >> i & 1
				if sb != 0 and j != mi:
					a[j] = a[j] ^ a[mi]
			index = index + 1
		res = 0
		for i in a:
			res = res ^ i
		return res


class Solution:

	def maxXor(self, a, n):
		index = 0
		for i in range(31, -1, -1):
			maxindex = index
			maxele = -999999999
			for j in range(index, n):
				if a[j] & 1 << i != 0 and a[j] > maxele:
					maxele = a[j]
					maxindex = j
			if maxele == -999999999:
				continue
			temp = a[index]
			a[index] = a[maxindex]
			a[maxindex] = temp
			maxindex = index
			for j in range(n):
				if a[j] & 1 << i != 0 and j != maxindex:
					a[j] = a[j] ^ a[maxindex]
			index = index + 1
		res = 0
		for i in range(n):
			res = res ^ a[i]
		return res


class Solution:

	def maxXor(self, a, n):
		BITS = 32
		index = 0
		for i in range(BITS - 1, -1, -1):
			max_index = index
			max_ele = -1000000000
			for j in range(index, n):
				if a[j] & 1 << i != 0 and a[j] > max_ele:
					max_ele = a[j]
					max_index = j
			if max_ele == -1000000000:
				continue
			temp = a[index]
			a[index] = a[max_index]
			a[max_index] = temp
			max_index = index
			for j in range(n):
				if j != max_index and a[j] & 1 << i != 0:
					a[j] = a[j] ^ a[max_index]
			index = index + 1
		res = 0
		for i in range(n):
			res = res ^ a[i]
		return res


from functools import reduce

class Solution:

	def maxXor(self, a, n):
		ind = 0
		for i in range(31, -1, -1):
			mx_ind = -1
			mx_ele = -float('inf')
			for j in range(ind, n):
				if a[j] & 1 << i != 0 and a[j] > mx_ele:
					mx_ele = a[j]
					mx_ind = j
			if mx_ele == -float('inf'):
				continue
			(a[ind], a[mx_ind]) = (a[mx_ind], a[ind])
			for j in range(n):
				if j != ind and a[j] & 1 << i != 0:
					a[j] = a[j] ^ a[ind]
			ind += 1
		return reduce(lambda a, b: a ^ b, a)


class Solution:

	def maxXor(self, a, n):
		start = 0
		for pos in range(16, -1, -1):
			bit = 1 << pos
			choose = None
			for i in range(start, n):
				if a[i] & bit:
					choose = i
					break
			if choose is not None:
				(a[start], a[choose]) = (a[choose], a[start])
				for i in range(n):
					if a[i] & bit and i != start:
						a[i] ^= a[start]
				start += 1
				if start == n:
					break
		ans = 0
		for i in range(n):
			ans ^= a[i]
		return ans


class Solution:

	def maxXor(self, set, n):
		index = 0
		for i in range(31, -1, -1):
			maxInd = index
			maxEle = -2147483648
			for j in range(index, n):
				if set[j] & 1 << i != 0 and set[j] > maxEle:
					maxEle = set[j]
					maxInd = j
			if maxEle == -2147483648:
				continue
			temp = set[index]
			set[index] = set[maxInd]
			set[maxInd] = temp
			maxInd = index
			for j in range(n):
				if j != maxInd and set[j] & 1 << i != 0:
					set[j] = set[j] ^ set[maxInd]
			index = index + 1
		res = 0
		for i in range(n):
			res = res ^ set[i]
		return res


INT_BITS = 32

def maxSubarrayXOR(set, n):
	index = 0
	for i in range(INT_BITS - 1, -1, -1):
		maxInd = index
		maxEle = -2147483648
		for j in range(index, n):
			if set[j] & 1 << i != 0 and set[j] > maxEle:
				maxEle = set[j]
				maxInd = j
		if maxEle == -2147483648:
			continue
		temp = set[index]
		set[index] = set[maxInd]
		set[maxInd] = temp
		maxInd = index
		for j in range(n):
			if j != maxInd and set[j] & 1 << i != 0:
				set[j] = set[j] ^ set[maxInd]
		index = index + 1
	res = 0
	for i in range(n):
		res = res ^ set[i]
	return res


class Solution:

	def maxXor(self, a, n):
		idx = 0
		for i in range(31, -1, -1):
			(maxidx, maxval) = (idx, -1)
			for j in range(idx, n):
				if a[j] & 1 << i != 0 and a[j] > maxval:
					(maxval, maxidx) = (a[j], j)
			if maxval < 0:
				continue
			(a[idx], a[maxidx]) = (a[maxidx], a[idx])
			for j in range(n):
				if j != idx and a[j] & 1 << i != 0:
					a[j] = a[j] ^ a[idx]
			idx += 1
		res = 0
		for x in a:
			res ^= x
		return res


class Solution:

	def maxXor(self, a, n):
		ix = 0
		for i in range(31, -1, -1):
			mx = -1 * float('inf')
			mxIx = -1
			for j in range(ix, n):
				if a[j] >> i & 1 and a[j] > mx:
					mx = a[j]
					mxIx = j
			el = a[mxIx]
			if mxIx == -1:
				continue
			(a[ix], a[mxIx]) = (a[mxIx], a[ix])
			mxIx = ix
			ix += 1
			for j in range(n):
				if a[j] >> i & 1 and j != mxIx:
					a[j] = a[j] ^ el
		res = a[0]
		for i in range(1, n):
			res = res ^ a[i]
		return res


class Solution:

	def maxXor(self, arr, n):
		j = 0
		for i in range(31, -1, -1):
			for k in range(j, n):
				if arr[k] & 1 << i:
					(arr[k], arr[j]) = (arr[j], arr[k])
					break
			if arr[j] & 1 << i:
				for k in range(j + 1, n):
					if arr[k] & 1 << i:
						arr[k] ^= arr[j]
				j += 1
			if j == n:
				break
		res = 0
		for i in range(j):
			res = max(res, res ^ arr[i])
		return res