1829. Maximum XOR for Each Query
Check out the leetcode for the problem statement.
Maximum XOR for Each Query - LeetCode
You are given a sorted array nums of n non-negative integers and an integer maximumBit. You want to perform the…
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.
Where N is the number of items in the list
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.
def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
for i in nums:
Time : O(N)
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^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. 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.
def getMaximumXor(self, nums):
for i in range(len(nums)):
Time : O(N)