Solving Algorithmic Problems

Description   Solution: Prefix XOR XORing a number with itself cancels itself out. i.e:  a = a ^ b ^ b Store the prefix XOR and use  pXor[j + 1] ^ pXor[i]  to get the range XOR of numbers between indices  i  and  j . n = length of arr ,  m = number of queries Time Complexity:  O(n + m) Space Complexity:  O(n)  excluding output function xorQueries ( arr, queries ) { let n = arr.length, pXor = Array (n + 1 ).fill( 0 ); for ( let i = 1 ; i <= n; i++) { pXor[i] = pXor[i - 1 ] ^ arr[i - 1 ]; } let answer = []; for ( let [left, right] of queries) { answer.push(pXor[right + 1 ] ^ pXor[left]); } return answer; };

Description   Solution: Line Sweep Use line sweep to get range updates in  O(1)  time, accumulating them with prefix sum at the end to get the actual values. Split the houses into three segments: The left part (nodes outside of the loop, on the left) The loop (nodes in ( x ,  y )) The right part (nodes outside of the loop on the right) Three scenarios to cover: From the left: Left nodes -> other left nodes Left nodes -> right nodes From the loop: Loop nodes -> left nodes Loop nodes -> other loop nodes Loop nodes -> right nodes From the right: Right nodes -> other right nodes (right -> left was covered from the left side already) Time Complexity:  O(n) Space Complexity:  O(n) var countOfPairs = function ( n, x, y ) { if (x > y) { let temp = x; x = y, y = temp; } let loopSize = y - x + 1 ; let sum = Array (n + 1 ).fill( 0 ); if (y - x <= 1 ) { for ( let node = 1 ; node < n; node++) { sum[ 1 ] +...