diff options
author | Jack Sangdahl <[email protected]> | 2024-11-03 00:01:49 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-11-03 00:01:49 -0600 |
commit | 64fa827c19c72e7a2f490e75856870a41d6b4c5f (patch) | |
tree | 43b6f938b62f0c7d4ff4f558586f998a9b6960dc /maximum_xor_query.py | |
parent | 20fb571e363b19bec8d6f595d471de8fdb01a95b (diff) | |
download | leetcode-64fa827c19c72e7a2f490e75856870a41d6b4c5f.tar.gz leetcode-64fa827c19c72e7a2f490e75856870a41d6b4c5f.zip |
1829. maximum xor for each query
Diffstat (limited to 'maximum_xor_query.py')
-rw-r--r-- | maximum_xor_query.py | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/maximum_xor_query.py b/maximum_xor_query.py new file mode 100644 index 0000000..1790c62 --- /dev/null +++ b/maximum_xor_query.py @@ -0,0 +1,31 @@ +# 1829. Maximum XOR for Each Query + +""" +you are given a sorted array 'nums' of 'n' non negative integers and an +integer 'maximumBit'. you want to perform the following query 'n' times: find +a non-negative integer 'k < 2^maximumBit' such that 'nums[0] ^ nums[1] ^ ... +^ nums[n]' is maximised. 'k' is the answer to the i'th query. remove the last +element from the current array 'nums'. return an array 'answer' where +'answer[i]' is the answer to the i'th query. +""" + + +class Solution(object): + def getMaximumXor(self, nums, maximumBit): + """ + :type nums: List[int] + :type maximumBit: int + :rtype: List[int] + """ + max_xor, arr_xor, ans = (1 << maximumBit) - 1, reduce(ixor, nums), [] + for i in range(len(nums) - 1, -1, -1): + ans.append(arr_xor ^ max_xor) + arr_xor ^= nums[i] + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.getMaximumXor(nums=[0, 1, 1, 3], maximumBit=2)) + print(obj.getMaximumXor(nums=[2, 3, 4, 7], maximumBit=3)) + print(obj.getMaximumXor(nums=[0, 1, 2, 2, 5, 7], maximumBit=3)) |