{"id":7868,"date":"2020-12-27T13:31:59","date_gmt":"2020-12-27T21:31:59","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7868"},"modified":"2020-12-27T13:45:22","modified_gmt":"2020-12-27T21:45:22","slug":"leetcode-421-maximum-xor-of-two-numbers-in-an-array","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/trie\/leetcode-421-maximum-xor-of-two-numbers-in-an-array\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 421. Maximum XOR of Two Numbers in an Array"},"content":{"rendered":"\n<p>Given an integer array&nbsp;<code>nums<\/code>, return&nbsp;<em>the maximum result of&nbsp;<code>nums[i] XOR nums[j]<\/code><\/em>, where&nbsp;<code>0 \u2264 i \u2264 j &lt; n<\/code>.<\/p>\n\n\n\n<p><strong>Follow up:<\/strong>&nbsp;Could you do this in&nbsp;<code>O(n)<\/code>&nbsp;runtime?<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [3,10,5,25,2,8]\n<strong>Output:<\/strong> 28\n<strong>Explanation:<\/strong> The maximum result is 5 XOR 25 = 28.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [0]\n<strong>Output:<\/strong> 0\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [2,4]\n<strong>Output:<\/strong> 6\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [8,10,2]\n<strong>Output:<\/strong> 10\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [14,70,53,83,49,91,36,80,92,51,66,70]\n<strong>Output:<\/strong> 127\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4<\/sup><\/code><\/li><li><code>0 &lt;= nums[i] &lt;= 2<sup>31<\/sup>&nbsp;- 1<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Trie<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(31*2*n)<br>Space complexity: O(31*2*n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Trie {\npublic:\n  Trie(): children(2) {}  \n  vector<unique_ptr<Trie>> children;\n};\nclass Solution {\npublic:\n  int findMaximumXOR(vector<int>& nums) {\n    Trie root;\n    \n    \/\/ Insert a number into the trie.\n    auto insert = [&](Trie* node, int num) {\n      for (int i = 31; i >= 0; --i) {\n        int bit = (num >> i) & 1;\n        if (!node->children[bit])\n          node->children[bit] = std::make_unique<Trie>();\n        node = node->children[bit].get();\n      }\n    };\n  \n    \/\/ Find max xor sum of num and another element in the array.\n    auto query = [&](Trie* node, int num) {\n      int sum = 0;\n      for (int i = 31; i >= 0; --i) {\n        int bit = (num >> i) & 1;\n        if (node->children[1 - bit]) {\n          sum += (1 << i);\n          node = node->children[1 - bit].get();\n        } else {\n          node = node->children[bit].get();\n        }\n      }\n      return sum;\n    };\n    \n    \/\/ Insert all numbers.\n    for (int x : nums) \n      insert(&root, x);\n    \n    int ans = 0;\n    \/\/ For each number find the maximum xor sum.\n    for (int x : nums) \n      ans = max(ans, query(&root, x));\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an integer array&nbsp;nums, return&nbsp;the maximum result of&nbsp;nums[i] XOR nums[j], where&nbsp;0 \u2264 i \u2264 j &lt; n. Follow up:&nbsp;Could you do this in&nbsp;O(n)&nbsp;runtime? Example 1:&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[680],"tags":[16,96,63],"class_list":["post-7868","post","type-post","status-publish","format-standard","hentry","category-trie","tag-bit","tag-trie","tag-xor","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7868","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7868"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7868\/revisions"}],"predecessor-version":[{"id":7872,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7868\/revisions\/7872"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7868"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7868"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7868"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}