Problem of The Day: Count the Number of Consistent Strings

Problem Statement

Brute Force - TLE

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

Intuition

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.

Approach

1. First, construct a prefix_xor array where each element at index i stores the XOR of all elements from index 0 to i in the original array.
2. For each query (left, right), we can efficiently compute the XOR of elements from index left to right using the relation: XOR(left, right) = prefix_xor[right] ^ prefix_xor[left - 1] If left == 0, then the XOR result is simply prefix_xor[right].

Complexity

• Time complexity:
  O(n + q) where n is the length of the array and q is the number of queries. Constructing the prefix_xor array takes O(n) time, and each query is resolved in constant time O(1), leading to O(q) for processing all queries.

• Space complexity:
  O(n) for storing the prefix_xor array.

Code

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

Editorial

Approach 1: Iterative Approach

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 Array

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