In this Leetcode Maximum XOR of Two Numbers in an Array problem solution we have given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.
Problem solution in Python.
class Solution: def findMaximumXOR(self, nums: List[int]) -> int: mask = 0 ans = 0 for i in range(31, -1, -1): mask = mask | 1 << i s = set() for num in nums: s.add(num & mask) start = ans | 1 << i for prefix in s: if start ^ prefix in s: ans = start return ans
Problem solution in Java.
class Solution { public int findMaximumXOR(int[] nums) { Node root = new Node(); insert(root, nums[0], 30); int ans = 0; for(int i=1;i<nums.length;i++){ ans = Math.max(ans, query(root, nums[i], 30)); insert(root, nums[i], 30); } return ans; } public class Node{ Node left, right; int lc, rc; public Node(){ this.left = null; this.right = null; this.lc = 0; this.rc = 0; } } void insert(Node node, int val, int level){ if(level==-1){ return; } if((val&(1<<level))>0){ if(node.right==null){ node.right = new Node(); } node.rc++; insert(node.right, val, level-1); }else{ if(node.left==null){ node.left = new Node(); } node.lc++; insert(node.left, val, level-1); } } int query(Node node, int val, int level){ if(level==-1){ return 0; } if((val&(1<<level))>0){ if(node.left!=null){ return query(node.left, val, level-1)|(1<<level); }else{ return query(node.right, val, level-1); } }else{ if(node.right!=null){ return query(node.right, val, level-1)|(1<<level); }else{ return query(node.left, val, level-1); } } } }
Problem solution in C++.
#define ll long long class Solution { public: struct Tries{ array<Tries *, 2> mp; }; void insert(Tries *root, int n){ for(int i=31; i>=0; i--){ int bit = (n&(1<<i)); if(bit) bit = 1; if(root->mp[bit] == NULL) root->mp[bit] = new Tries(); root = root->mp[bit]; } } ll findMax(Tries *root, ll n){ ll ans = 0; for(int i=31; i>=0; i--){ int bit = (n&(1<<i)); if(bit) bit = 1; if(root->mp[!bit]){ ans += (1<<i); root = root->mp[!bit]; } else root = root->mp[bit]; } return ans; } int findMaximumXOR(vector<int>& nums) { int ans = 0; Tries *root = new Tries(); for(int i : nums) insert(root, i); for(int i : nums){ int x = findMax(root, i); ans = max(ans, x); } return ans; } };
Problem solution in C.
#define MAX_BIT 30 struct tree{ struct tree *leaf[2]; /* bit 0 --> leaf 0 ; bit 1 --> leaf 1*/ }; static void buildTree(struct tree *root, int *nums, int numsSize) { int i; int j; int bit_val; struct tree *node = NULL; for (i = 0; i < numsSize; i++) { node = root; for (j = MAX_BIT; j >= 0; j--) { bit_val = nums[i] >> j & 1; if (!node->leaf[bit_val]) node->leaf[bit_val] = calloc(1, sizeof(*root)); node = node->leaf[bit_val]; } } } void freeTree(struct tree *root) { if (!root) return; if (root->leaf[0]); freeTree(root->leaf[0]); if (root->leaf[1]) freeTree(root->leaf[1]); free(root); } int findMaximumXOR(int* nums, int numsSize) { struct tree root = {0}; int i; int j; struct tree *node = NULL; int max = 0; int cur = 0; int bit_val = 0; if (1 == numsSize) return 0; buildTree(&root, nums, numsSize); for (i = 0; i < numsSize; i++) { cur = 0; node = &root; for (j = MAX_BIT; j >= 0; j--) { bit_val = nums[i] >> j & 1; if (node->leaf[!bit_val]) { cur += 1 << j; node = node->leaf[!bit_val]; } else { node = node->leaf[bit_val]; } } if (cur > max) max = cur; } freeTree(root.leaf[0]); freeTree(root.leaf[1]); return max; }
0 Comments