Subramanya's Digital Garden

Recent Notes

1310. XOR Queries of a Subarray

2 min read

links: Algorithms MOC

Problem

You are given an array arr of positive integers. You are also given the array queries where queries[i] = [lefti, righti].

For each query i compute the XOR of elements from lefti to righti (that is, arr[lefti] XOR arr[lefti + 1] XOR ... XOR arr[righti] ).

Return an array answer where answer[i] is the answer to the ith query.

Approach

  1. You can try the naive approach by looping through queries and building answer by looping arr from start to end
  2. One of the nice thing about XOR is x ^ y ^ x = x.

Consider an arr = [1,3,4,8] Now calculate the prefix xor of arr

If the query is [1, 2] this can be derived as prefixXOR[2] ^ prefixXOR[0]

  • prefixXOR[2] gives the XOR till 2
  • prefixXOR[0] gives the XOR till 1

From the above logic x ^ y ^ x

prefixXOR[2] can be considered as x ^ y prefixXOR[0] can be considered as x

Now the result will be y which is the desired solution

Naive Approach

/**
 * @param {number[]} arr
 * @param {number[][]} queries
 * @return {number[]}
 */
var xorQueries = function(arr, queries) {
  let answer = new Array();
  queries.forEach((elem, index) => {
    const [left, right] = elem;
    let xor;
    if (left === right) {
      xor = arr[left];
      answer.push(xor);
      return;
    }
    for (let i = left + 1; i <= right; i++) {
      if (xor !== undefined) {
        xor = xor ^ arr[i];
      } else {
        xor = arr[i - 1] ^ arr[i];
      }
    }
    xor
    answer.push(xor);
  });
  return answer;
};

XOR Logic Approach

/**
 * @param {number[]} arr
 * @param {number[][]} queries
 * @return {number[]}
 */
var xorQueries = function(arr, queries) {
  let result = new Array();
  
  for(let i = 1; i < arr.length; ++i) {
    arr[i] ^= arr[i - 1]
  }
  
  queries.forEach((elem, index) => {
    const [left, right] = elem
    if(left == 0) {
      result.push(arr[right])
    } else {
      result.push(arr[right] ^ arr[left - 1])
    }
  })
  
  return result
};

tags: bit-manipulation array prefix-sum

sources:

Graph View