Solving Algorithmic Problems

Description   Solution: Bitwise Trie & Two Pointers Sort nums in asc order. For each  nums[i] , move up index  j  while  nums[j] - nums[i] <= nums[i] . Use a bitwise trie to find the maximum bitwise XOR, which is a greedy strategy of taking the opposite bit whenever possible. n = length of nums ,  m = max(nums[i]) Time Complexity:  O(n log(m)) Space Complexity:  O(m) var maximumStrongPairXor = function ( nums ) { nums.sort( ( a, b ) => a - b); let n = nums.length, trie = new BitwiseTrie(), maxXor = 0 ; for ( let i = 0 , j = 0 ; i < n; i++) { if (i > 0 ) trie.removeNum(nums[i - 1 ]); while (j < n && nums[j] - nums[i] <= nums[i]) { trie.addNum(nums[j]); j++; } maxXor = Math .max(maxXor, trie.maxXor(nums[i])); } return maxXor; }; class TrieNode { constructor ( ) { this .children = Array ( 2 ); this .num = null ; this .count = 0 ; } } class BitwiseTrie ...

Description   Solution: XOR For each  pref[i] , we need to find the number where  pref[i - 1] ^ ? = pref[i] . Look at individual bits of  pref[i - 1]  and  pref[i]  and construct the number we need: If the bits are the same, we must take bit  0 . If the bits are different, we must take bit  1 . Notice that the bits we need to take are actually the same as the result of XORing them together. 1 ^ 1 = 0 0 ^ 0 = 0 1 ^ 0 = 1 0 ^ 1 = 1 Therefore, we can XOR each  pref[i - 1]  and  pref[i]  to get the answers. Time Complexity:  O(n)  229ms Space Complexity:  O(1)  (not including output) 74.2MB var findArray = function ( pref ) { let n = pref.length, res = Array (n); res[ 0 ] = pref[ 0 ]; for ( let i = 1 ; i < n; i++) { res[i] = pref[i - 1 ] ^ pref[i]; } return res; };