Problem of The Day: Count the Number of Consistent Strings
Problem StatementPermalink
Brute Force - TLEPermalink
class Solution:
def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
N = len(queries)
res = [0] * N
for i, [left, right] in enumerate(queries):
res[i] = arr[left]
for j in range(left + 1, right + 1):
res[i] ^= arr[j]
return res
IntuitionPermalink
The problem requires calculating the XOR for a subarray in an efficient manner. A brute force approach would involve calculating the XOR for each query by iterating through the elements in the given range. However, this approach would be inefficient for multiple queries. We can optimize the solution using a prefix XOR array, which allows us to compute the XOR for any subarray in constant time.
ApproachPermalink
- First, construct a
prefix_xor
array where each element at indexi
stores the XOR of all elements from index0
toi
in the original array. - For each query
(left, right)
, we can efficiently compute the XOR of elements from indexleft
toright
using the relation: XOR(left, right) = prefix_xor[right] ^ prefix_xor[left - 1] Ifleft == 0
, then the XOR result is simplyprefix_xor[right]
.
ComplexityPermalink
-
Time complexity:
O(n + q)
wheren
is the length of the array andq
is the number of queries. Constructing theprefix_xor
array takesO(n)
time, and each query is resolved in constant timeO(1)
, leading toO(q)
for processing all queries. -
Space complexity:
O(n)
for storing theprefix_xor
array.
CodePermalink
class Solution:
def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
prefix_xor = []
curr = 0
N = len(arr)
res = []
for num in arr:
curr ^= num
prefix_xor.append(curr)
for left, right in queries:
idx = left - 1
excluded_val = prefix_xor[idx] if idx >= 0 else 0
res.append(excluded_val ^ prefix_xor[right])
return res
EditorialPermalink
Approach 1: Iterative ApproachPermalink
class Solution:
def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
result = []
# Process each query
for q in queries:
xor_sum = 0
# Calculate XOR for the range [q[0], q[1]]
for i in range(q[0], q[1] + 1):
xor_sum ^= arr[i]
result.append(xor_sum)
return result
Approach 2: Prefix XOR ArrayPermalink
class Solution:
def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
# Build prefix XOR array
prefix_xor = [0] * (len(arr) + 1)
for i in range(len(arr)):
prefix_xor[i + 1] = prefix_xor[i] ^ arr[i]
# Store the XOR result for each query in a variable
result = [prefix_xor[r + 1] ^ prefix_xor[l] for l, r in queries]
return result