How to Answer: Can you answer each query and return in an array?
Advice and answer examples written specifically for a Javascript Beginner Level Bit Manipulation job interview.
2. Can you answer each query and return in an array?
This interview question shows the developer's ability to work with JavaScript operators.
You are given an array arr of positive integers of length n. You are also given an array queries where queries[i] = [li, ri]. To answer queries[i], you XOR all the numbers arr from index li to ri (both inclusive), that is, arr[li] XOR arr[li + 1] XOR … XOR arr[ri]. Your task is to answer each query and return their result in an array.
/*Example*/
Given:
arr = [1, 3, 4, 8]
queries = [[0, 1], [1, 2], [0, 3] ,[3, 3]]
Expected:- [2, 7, 14, 8]Solution:
We will create an array prefixXors of length n. prefixXors[i] is the XOR of all numbers in arr from index 0 to i. Thus,
prefixXors[i] = prefixXors[i - 1] ^ arr[i]
Now finding the XOR of numbers between range li and ri is easy:
ans for ith query = XOR of numbers from index li to ri
= (XOR of numbers from index li to ri)
^ (XOR of numbers from index 0 to li - 1)
^ (XOR of numbers from index 0 to li - 1) // because a ^ a = 0
= (XOR of numbers from index 0 to ri)
^ (XOR of numbers from index 0 to li - 1)
= prefixXors[ri] ^ prefixXors[li - 1]
/**
* @param {number[]} arr
* @param {number[][]} queries
* @return {number[]}
*/
function xorQueries(arr, queries) {
const n = arr.length
const prefixXors = new Array(n)
prefixXors[0] = arr[0]
for (let i = 1; i < n; i++) {
prefixXors[i] = prefixXors[i - 1] ^ arr[i]
}
const result = []
for (const [l, r] of queries) {
let ans = prefixXors[r]
ans ^= l === 0 ? 0 : prefixXors[l - 1]
result.push(ans)
}
return result
}Time complexity- O(n + queries.length)
Space complexity- O(n)
Written by S. Kumar on May 22nd, 2021