From 32face77eb9aea8b03b3ce869e2d649e9070df63 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Thu, 12 Sep 2024 20:25:21 -0600 Subject: 1310. xor queries of a subarray --- xor_queries_subarray.c | 42 ++++++++++++++++++++++++++++++++++++++++++ xor_queries_subarray.py | 26 ++++++++++++++++++++++++++ 2 files changed, 68 insertions(+) create mode 100644 xor_queries_subarray.c create mode 100644 xor_queries_subarray.py diff --git a/xor_queries_subarray.c b/xor_queries_subarray.c new file mode 100644 index 0000000..616afc4 --- /dev/null +++ b/xor_queries_subarray.c @@ -0,0 +1,42 @@ +// 1310. XOR Queries of a Subarray +#include "leetcode.h" + +/* + * you are given an array 'arr' of positive integers. you are also given the + * array 'queries' where 'queries[i] = [left_i, right_i]'. for each query 'i' + * compute the xor of elements from 'left_i' to 'right_i'. return an array + * 'answer' where 'answer[i]' is the answer to the i'th query + */ + +int *xorQueries(int *arr, int arrSize, int **queries, int queriesSize, + int *queriesColSize, int *returnSize) { + int *ans = (int *)malloc(queriesSize * sizeof(int)); + int *prefix = (int *)calloc(arrSize, sizeof(int)); + for (int i = 0; i < arrSize; i++) + prefix[i] = !i ? arr[i] : prefix[i - 1] ^ arr[i]; + for (int i = 0; i < queriesSize; i++) { + int left = queries[i][0], right = queries[i][1]; + ans[i] = !left ? prefix[right] : prefix[right] ^ prefix[left - 1]; + } + *returnSize = queriesSize; + free(prefix); + return ans; +} + +int main() { + int a1[] = {1, 3, 4, 8}, q1[4][2] = {{0, 1}, {1, 2}, {0, 3}, {3, 3}}, + qcs1 = 4, rs1; + int a2[] = {4, 8, 2, 10}, q2[4][2] = {{2, 3}, {1, 3}, {0, 0}, {0, 3}}, + qcs2 = 4, rs2; + int *xq1 = + xorQueries(a1, ARRAY_SIZE(a1), (int **)q1, ARRAY_SIZE(q1), &qcs1, &rs1); + int *xq2 = + xorQueries(a2, ARRAY_SIZE(a2), (int **)q2, ARRAY_SIZE(q2), &qcs2, &rs2); + for (int i = 0; i < rs1; i++) + printf("%d ", xq1[i]); // expect: 2 7 14 8 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", xq2[i]); // expect: 8 0 4 4 + printf("\n"); + free(xq1), free(xq2); +} diff --git a/xor_queries_subarray.py b/xor_queries_subarray.py new file mode 100644 index 0000000..2c37821 --- /dev/null +++ b/xor_queries_subarray.py @@ -0,0 +1,26 @@ +# 1310. XOR Queries of a Subarray + +""" +you are given an array 'arr' of positive integers. you are also given the +array 'queries' where 'queries[i] = [left_i, right_i]'. for each query 'i' +compute the xor of elements from 'left_i' to 'right_i'. return an array +'answer' where 'answer[i]' is the answer to the i'th query +""" + + +class Solution(object): + def xorQueries(self, arr, queries): + """ + :type arr: List[int] + :type queries: List[List[int]] + :rtype: List[int] + """ + for i in range(len(arr) - 1): + arr[i + 1] ^= arr[i] + return [arr[j] ^ arr[i - 1] if i else arr[j] for i, j in queries] + + +if __name__ == "__main__": + obj = Solution() + print(obj.xorQueries(arr=[1, 3, 4, 8], queries=[[0, 1], [1, 2], [0, 3], [3, 3]])) + print(obj.xorQueries(arr=[4, 8, 2, 10], queries=[[2, 3], [1, 3], [0, 0], [0, 3]])) -- cgit v1.2.3