# 1829. Maximum XOR for Each Query

Check out the leetcode for the problem statement.

Approach1 :

Bruteforce

For values from 0 to 2^maxbit-1 , we check which is the value that gives the max XOR with XOR of all elements in the array. And then remove the last element in the list . This is repeated till the array is empty.

*Time :O(N*2^(maxbit-1))*

*Space: O(N)*

Where N is the number of items in the list

Approach 2:

We first take XOR of all the elements in the array. And check which is the k value that satisfy the condition by checking all the bit position from maxbit-1 th position to 0. This is repeated by popping the last element in the list.

`class Solution:`

def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:

xor_=0

result=[]

start=1<<(maximumBit-1)

for i in nums:

xor_^=i

while(True):

if(not nums):

return( result)

val=0

mask=start

while(mask):

val<<=1

if(xor_&mask!=0):

val|=0

else:

val|=1

mask>>=1

result.append(val)

xor_^=nums[-1]

nums.pop(-1);

*Time : O(N)*

*Space: O(N)*

Approach 3:

More optimized solution

We start this problem in reverse fashion . We start from the first number that is from the number 0th position in array , and we XOR it with (2**maxbit)-1,(that is max value possible with , number of bits =maxbits,which is same as (1<<maximumBit)-1 ) , let it be the mask . Then if we XOR between them , that is nums[0]^mask , we get the k giving the maximum XOR . Similarly for next iteration , we do it for first 2 numbers in the array. Which is same as saving the previous XOR result , in the mask and XORING it with the current number which is nums[1]. This is continued till end of array. Also to save the space the result obtained in each iteration is stored in the same nums lis . Finally , the required result is the got by reversing the nums list.

`class Solution:`

def getMaximumXor(self, nums):

mask=(1<<maximumBit)-1

for i in range(len(nums)):

mask^=nums[i]

nums[i]=mask

return(nums[::-1])

*Time : O(N)*

*Space: O(1)*