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: Greedy - N Most Significant Bits in num1 Find  n , the number of 1-bits in  num2 . Create a number with the  n  most significant bits of  num1 . (Since  1^1 = 0 , we will be minimizing the result by removing the most significant bits) If  num1  has less than  n  1-bits, take the least significant bits. (If there are no bits to remove, we need to take the bits that add the least value) Time Complexity:  O(32)  =  O(1) Space Complexity:  O(1) var minimizeXor = function ( num1, num2 ) { let n = countOnes(num2), res = 0 , ones = 0 ; // Take the most significant 1-bits in num1 for ( let i = 31 ; i >= 0 ; i--) { if (ones === n) break ; if (((num1 >> i) & 1 ) === 1 ) { res |= ( 1 << i); ones++; } } // Take the least significant bits if there are no more 1-bits in num1 for ( let i = 0 ; i <= 31 ; i++) { if (ones === n) b...

Description   Solution: Count Individual Bits To have a bitwise AND sum larger than 0, we only need one bit that hasn't been cancelled out. Populate an array count, where  count[i] indicates the number of candidates where the ith bit is 1. Get the maximum count. Time Complexity:  O(n) Space Complexity:  O(1) var largestCombination = function ( candidates ) { let count = Array ( 32 ).fill( 0 ); for ( let num of candidates) { let number = num, pos = 0 ; while (number > 0 ) { let bit = number & 1 ; if (bit) count[pos]++; number = number >> 1 ; pos++; } } return Math .max(...count); }; javascript