{"id":7871,"date":"2020-12-27T13:54:20","date_gmt":"2020-12-27T21:54:20","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7871"},"modified":"2020-12-28T00:12:11","modified_gmt":"2020-12-28T08:12:11","slug":"leetcode-1707-maximum-xor-with-an-element-from-array","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/trie\/leetcode-1707-maximum-xor-with-an-element-from-array\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1707. Maximum XOR With an Element From Array"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1707. Maximum XOR With an Element From Array - \u5237\u9898\u627e\u5de5\u4f5c EP377\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/k0e9tM7gU3E?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>You are given an array&nbsp;<code>nums<\/code>&nbsp;consisting of non-negative integers. You are also given a&nbsp;<code>queries<\/code>&nbsp;array, where&nbsp;<code>queries[i] = [x<sub>i<\/sub>, m<sub>i<\/sub>]<\/code>.<\/p>\n\n\n\n<p>The answer to the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;query is the maximum bitwise&nbsp;<code>XOR<\/code>&nbsp;value of&nbsp;<code>x<sub>i<\/sub><\/code>&nbsp;and any element of&nbsp;<code>nums<\/code>&nbsp;that does not exceed&nbsp;<code>m<sub>i<\/sub><\/code>. In other words, the answer is&nbsp;<code>max(nums[j] XOR x<sub>i<\/sub>)<\/code>&nbsp;for all&nbsp;<code>j<\/code>&nbsp;such that&nbsp;<code>nums[j] &lt;= m<sub>i<\/sub><\/code>. If all elements in&nbsp;<code>nums<\/code>&nbsp;are larger than&nbsp;<code>m<sub>i<\/sub><\/code>, then the answer is&nbsp;<code>-1<\/code>.<\/p>\n\n\n\n<p>Return&nbsp;<em>an integer array&nbsp;<\/em><code>answer<\/code><em>&nbsp;where&nbsp;<\/em><code>answer.length == queries.length<\/code><em>&nbsp;and&nbsp;<\/em><code>answer[i]<\/code><em>&nbsp;is the answer to the&nbsp;<\/em><code>i<sup>th<\/sup><\/code><em>&nbsp;query.<\/em><\/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 = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]\n<strong>Output:<\/strong> [3,3,7]\n<strong>Explanation:<\/strong>\n1) 0 and 1 are the only two integers not greater than 1. 0 XOR 3 = 3 and 1 XOR 3 = 2. The larger of the two is 3.\n2) 1 XOR 2 = 3.\n3) 5 XOR 2 = 7.\n<\/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 = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]\n<strong>Output:<\/strong> [15,-1,5]\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, queries.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>queries[i].length == 2<\/code><\/li><li><code>0 &lt;= nums[j], x<sub>i<\/sub>, m<sub>i<\/sub>&nbsp;&lt;= 10<sup>9<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Trie on the fly<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1707-ep377-1.png\" alt=\"\" class=\"wp-image-7874\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1707-ep377-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1707-ep377-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1707-ep377-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1707-ep377-2.png\" alt=\"\" class=\"wp-image-7875\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1707-ep377-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1707-ep377-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1707-ep377-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1707-ep377-3.png\" alt=\"\" class=\"wp-image-7876\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1707-ep377-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1707-ep377-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1707-ep377-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>Similar idea to <a href=\"https:\/\/zxi.mytechroad.com\/blog\/trie\/leetcode-421-maximum-xor-of-two-numbers-in-an-array\/\">https:\/\/zxi.mytechroad.com\/blog\/trie\/leetcode-421-maximum-xor-of-two-numbers-in-an-array\/<\/a><\/p>\n\n\n\n<p>We can build the trie on the fly by sorting nums in ascending order and queries by its limit, insert nums into the trie up the limit.<\/p>\n\n\n\n<p>Time complexity: O(nlogn + QlogQ)<br>Space complexity: O(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{nullptr, nullptr} {}  \n  Trie* children[2];\n};\nclass Solution {\npublic:\n  vector<int> maximizeXor(vector<int>& nums, vector<vector<int>>& queries) {\n    const int n = nums.size();\n    sort(begin(nums), end(nums));    \n    \n    const int Q = queries.size();\n    for (int i = 0; i < Q; ++i)\n      queries[i].push_back(i);\n    sort(begin(queries), end(queries), [](const auto&#038; q1, const auto&#038; q2) {\n      return q1[1] < q2[1];\n    });\n    \n    Trie root;    \n    auto insert = [&#038;](int num) {\n      Trie* node = &root; \n      for (int i = 31; i >= 0; --i) {\n        int bit = (num >> i) & 1;\n        if (!node->children[bit])\n          node->children[bit] = new Trie();\n        node = node->children[bit];\n      }\n    };\n        \n    auto query = [&](int num) {\n      Trie* node = &root;\n      int sum = 0;\n      for (int i = 31; i >= 0; --i) {\n        if (!node) return -1;\n        int bit = (num >> i) & 1;\n        if (node->children[1 - bit]) {\n          sum |= (1 << i);\n          node = node->children[1 - bit];\n        } else {\n          node = node->children[bit];\n        }\n      }\n      return sum;\n    };\n    \n    vector<int> ans(Q);\n    int i = 0;\n    for (const auto& q : queries) {\n      while (i < n &#038;&#038; nums[i] <= q[1]) insert(nums[i++]);\n      ans[q[2]] = query(q[0]);\n    }  \n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an array&nbsp;nums&nbsp;consisting of non-negative integers. You are also given a&nbsp;queries&nbsp;array, where&nbsp;queries[i] = [xi, mi]. The answer to the&nbsp;ith&nbsp;query is the maximum bitwise&nbsp;XOR&nbsp;value&#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":[217,140,15,96],"class_list":["post-7871","post","type-post","status-publish","format-standard","hentry","category-trie","tag-hard","tag-query","tag-sorting","tag-trie","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7871","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=7871"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7871\/revisions"}],"predecessor-version":[{"id":7877,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7871\/revisions\/7877"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7871"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7871"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7871"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}