aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-12 20:25:21 -0600
committerJack Sangdahl <[email protected]>2024-09-12 20:25:21 -0600
commit32face77eb9aea8b03b3ce869e2d649e9070df63 (patch)
treef692412c8b45329d5aea4d830944f028e608d79d
parent5003fa90718ed23eb1101ec320671aacef128ac2 (diff)
downloadleetcode-32face77eb9aea8b03b3ce869e2d649e9070df63.tar.gz
leetcode-32face77eb9aea8b03b3ce869e2d649e9070df63.zip
1310. xor queries of a subarray
-rw-r--r--xor_queries_subarray.c42
-rw-r--r--xor_queries_subarray.py26
2 files changed, 68 insertions, 0 deletions
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]]))