diff options
-rw-r--r-- | maximum_xor_query.c | 41 | ||||
-rw-r--r-- | maximum_xor_query.py | 31 |
2 files changed, 72 insertions, 0 deletions
diff --git a/maximum_xor_query.c b/maximum_xor_query.c new file mode 100644 index 0000000..5c9b62c --- /dev/null +++ b/maximum_xor_query.c @@ -0,0 +1,41 @@ +// 1829. Maximum XOR for Each Query +#include "leetcode.h" + +/* + * 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. + */ + +int *getMaximumXor(int *nums, int numsSize, int maximumBit, int *returnSize) { + int *ans = (int *)malloc(numsSize * sizeof(int)); + *returnSize = numsSize; + int max = pow(2, maximumBit) - 1; + for (int i = 1; i < numsSize; i++) + nums[i] ^= nums[i - 1]; + for (int i = 0; i < numsSize; i++) + ans[i] = nums[numsSize - i - 1] ^ max; + return ans; +} + +int main() { + int n1[] = {0, 1, 1, 3}, rs1; + int n2[] = {2, 3, 4, 7}, rs2; + int n3[] = {0, 1, 2, 2, 5, 7}, rs3; + int *gmx1 = getMaximumXor(n1, ARRAY_SIZE(n1), 2, &rs1); + int *gmx2 = getMaximumXor(n2, ARRAY_SIZE(n2), 3, &rs2); + int *gmx3 = getMaximumXor(n3, ARRAY_SIZE(n3), 3, &rs3); + for (int i = 0; i < rs1; i++) + printf("%d ", gmx1[i]); // expect: 0 3 2 3 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", gmx2[i]); // expect: 5 2 6 5 + printf("\n"); + for (int i = 0; i < rs3; i++) + printf("%d ", gmx3[i]); // expect: 4 3 6 4 6 7 + printf("\n"); + free(gmx1), free(gmx2), free(gmx3); +} 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)) |