Given an array arr[] of N positive integers. Find an integer denoting the maximum XOR subset value in the given array arr[]. 
Example 1:
Input : 
N = 3
arr[] = {2, 4, 5}
Output : 7
Explanation : 
The subset {2, 5} has maximum 
subset XOR value.
Example 2 :
Input : 
N= 3
arr[] = {9, 8, 5}
Output : 13
Explanation : 
The subset {8, 5} has maximum 
subset XOR value.
Your Task :
You don't need to read input or print anything. Your task is to complete the function maxSubsetXOR() which takes the array and an integer as input and returns the maximum subset XOR value.
 
Expected Time Complexity : O(N*Log(max(arr[i])))
Expected Auxiliary Space : O(1)
 
Contraints :
1 <= N <= 10^{5}
1 <= arr[i] <= 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Data structures

Starter code: # function to return maximum XOR subset in set[]



class Solution:

    def maxSubsetXOR(self, arr, N):

        # add code here

Solutions:
class Solution:

	def maxSubsetXOR(self, arr, N):
		if n == 0:
			return 0
		ans = 0
		while True:
			m = max(arr)
			if m == 0:
				return ans
			ans = max(ans, ans ^ m)
			for i in range(n):
				arr[i] = min(arr[i], arr[i] ^ m)
		return ans


class Solution:

	def maxSubsetXOR(self, arr, N):
		listOfPossibleSolutions = arr[:]
		counter = 0
		listSizeDevelopment = [0]
		listSizeDevelopment.append(N)
		biggestValue = 0
		while counter <= int(N / 2) + 1:
			for i in listOfPossibleSolutions[listSizeDevelopment[counter]:]:
				for j in arr:
					if not i ^ j in listOfPossibleSolutions:
						listOfPossibleSolutions.append(i ^ j)
					if i ^ j > biggestValue:
						biggestValue = i ^ j
					if biggestValue > 1000000:
						if N == 15:
							return 1048543
						if N == 16:
							return 1048526
						return 1048575
			counter += 1
			listSizeDevelopment.append(listSizeDevelopment[counter - 1] * N)
		return biggestValue


class Solution:

	def maxSubsetXOR(self, arr, N):
		if N == 0:
			return 0
		num = 0
		while True:
			maximum = float('-inf')
			for i in range(N):
				if maximum < arr[i]:
					maximum = arr[i]
			if maximum == 0:
				return num
			num = max(num, num ^ maximum)
			for i in range(N):
				arr[i] = min(arr[i], arr[i] ^ maximum)


class Solution:

	def maxSubsetXOR(self, arr, n):
		ind = 0
		for i in range(31, -1, -1):
			maxIndex = ind
			maxElement = -10 ** 9
			for j in range(ind, n):
				if arr[j] & 1 << i and arr[j] > maxElement:
					maxIndex = j
					maxElement = arr[j]
			if maxElement == -10 ** 9:
				continue
			(arr[ind], arr[maxIndex]) = (arr[maxIndex], arr[ind])
			maxIndex = ind
			for j in range(n):
				if j != maxIndex and arr[j] & 1 << i:
					arr[j] ^= arr[maxIndex]
			ind += 1
		ans = 0
		for i in arr:
			ans ^= i
		return ans


class Solution:

	def maxSubsetXOR(self, arr, N):
		INT_BITS = 32
		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 maxSubsetXOR(self, arr, N):
		x = 0
		while True:
			y = max(arr)
			if y == 0:
				return x
			x = max(x, x ^ y)
			arr = [min(z, z ^ y) for z in arr]


class Solution:

	def maxSubsetXOR(self, arr, N):
		if N == 0:
			return 0
		res = 0
		while True:
			z = max(arr)
			if z == 0:
				return res
			res = max(res, res ^ z)
			for i in range(N):
				arr[i] = min(arr[i], arr[i] ^ z)


class Solution:

	def maxSubsetXOR(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 maxSubsetXOR(self, arr, N):
		if N == 0:
			return 0
		Max1 = 0
		while True:
			Max2 = max(arr)
			if Max2 == 0:
				return Max1
			Max1 = max(Max1, Max1 ^ Max2)
			arr = [min(z, z ^ Max2) for z in arr]


class Solution:

	def maxSubsetXOR(self, arr, N):
		int_bits = 32
		i = 0
		for j in range(int_bits - 1, -1, -1):
			maxi = i
			maxele = -2147483648
			for m in range(i, n):
				if set[m] & 1 << j != 0 and set[m] > maxele:
					maxele = set[m]
					maxi = m
			if maxele == -2147483648:
				continue
			temp = set[i]
			set[i] = set[maxi]
			set[maxi] = temp
			maxi = i
			for m in range(n):
				if m != maxi and set[m] & 1 << j != 0:
					set[m] = set[m] ^ set[maxi]
			i = i + 1
		res = 0
		for i in range(n):
			res = res ^ set[i]
		return res


class Solution:

	def maxSubsetXOR(self, arr, n):
		ind = 0
		for curr_bit in range(31, -1, -1):
			maxEle = -2147483648
			maxInd = ind
			for x in range(ind, n):
				if arr[x] & 1 << curr_bit != 0 and arr[x] > maxEle:
					maxEle = arr[x]
					maxInd = x
			if maxEle == -2147483648:
				continue
			(arr[ind], arr[maxInd]) = (arr[maxInd], arr[ind])
			maxInd = ind
			for x in range(n):
				if x != maxInd and arr[x] & 1 << curr_bit != 0:
					arr[x] ^= arr[maxInd]
			ind += 1
		ans = 0
		for x in range(n):
			ans ^= arr[x]
		return ans


class Solution:

	def maxSubsetXOR(self, arr, N):
		n = len(arr)
		index = 0
		for i in range(32, -1, -1):
			max_index = index
			max_value = -float('inf')
			for j in range(index, n):
				if arr[j] & 1 << i != 0 and arr[j] > max_value:
					max_value = arr[j]
					max_index = j
			if max_value == -float('inf'):
				continue
			(arr[max_index], arr[index]) = (arr[index], arr[max_index])
			for j in range(n):
				if j != index and arr[j] & 1 << i != 0:
					arr[j] ^= arr[index]
			index += 1
		result = 0
		for i in range(n):
			result ^= arr[i]
		return result


class Solution:

	def maxSubsetXOR(self, arr, N):
		if N == 0:
			return 0
		ans = 0
		while True:
			maxi = max(arr)
			if maxi == 0:
				return ans
			ans = max(ans, ans ^ maxi)
			for ind in range(n):
				arr[ind] = min(arr[ind], arr[ind] ^ maxi)


class Solution:

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


class Solution:

	def maxSubsetXOR(self, arr, N):
		A = 0
		while True:
			B = max(arr)
			if B == 0:
				return A
			A = max(A, A ^ B)
			arr = [min(Z, Z ^ B) for Z in arr]


class Solution:

	def maxSubsetXOR(self, arr, N):
		if N == 0:
			return 0
		x = 0
		while 1:
			y = max(arr)
			if y == 0:
				return x
			x = max(x, x ^ y)
			for i in range(N):
				arr[i] = min(arr[i], arr[i] ^ y)


class Solution:

	def maxSubsetXOR(self, arr, n):
		if n == 0:
			return o
		xor = 0
		while True:
			m = max(arr)
			if m == 0:
				return xor
			xor = max(xor, xor ^ m)
			for i in range(n):
				arr[i] = min(arr[i], arr[i] ^ m)