XOR Queries of a Subarray Solution in Java

Problem Description

Welcome to the world of XOR Queries of a Subarray! Imagine you’re at a party, and you want to know how many times your friend Bob has told a joke between two specific moments in time. But instead of counting the jokes, you’re going to use the magical XOR operation. Yes, that’s right! XOR is like the party trick that only the cool kids know about.

In this problem, you’re given an array of integers, and you need to answer multiple queries. Each query asks for the XOR of all elements in a subarray defined by two indices. It’s like asking, “Hey, what’s the vibe of the jokes told between these two moments?” Spoiler alert: the vibe is always a bit quirky!

Code Solution


class Solution {
  public int[] xorQueries(int[] arr, int[][] queries) {
    int[] ans = new int[queries.length];
    int[] xors = new int[arr.length + 1];

    for (int i = 0; i < arr.length; ++i)
      xors[i + 1] = xors[i] ^ arr[i];

    int i = 0;
    for (int[] query : queries) {
      final int left = query[0];
      final int right = query[1];
      ans[i++] = xors[left] ^ xors[right + 1];
    }

    return ans;
  }
}

Approach Explanation

The approach here is as clever as a fox wearing glasses! We first create a prefix XOR array, which allows us to compute the XOR of any subarray in constant time. The prefix XOR array is built by XORing each element with the previous cumulative XOR. When a query comes in, we simply XOR the two ends of the range using the prefix array. Voilà! Instant results!

Time and Space Complexity

Time Complexity: O(n + q), where n is the length of the array and q is the number of queries. We spend O(n) time to build the prefix XOR array and O(q) time to answer the queries.

Space Complexity: O(n), for storing the prefix XOR array.

Real-World Example

Let’s say you’re at a comedy club, and you want to know how many jokes were told between two specific comedians. Instead of counting each joke, you could use the XOR operation to get the “joke vibe” of that segment. If the vibe is positive, it means the jokes were good; if it’s negative, well, maybe it’s time to leave the club!