1829. Maximum XOR for Each Query

Check out the leetcode for the problem statement.

Maximum XOR for Each Query - LeetCode

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)