{"id":8509,"date":"2021-08-07T00:17:29","date_gmt":"2021-08-07T07:17:29","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8509"},"modified":"2021-08-07T00:18:07","modified_gmt":"2021-08-07T07:18:07","slug":"leetcode-1879-minimum-xor-sum-of-two-arrays","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1879-minimum-xor-sum-of-two-arrays\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1879. Minimum XOR Sum of Two Arrays"},"content":{"rendered":"\n<p>You are given two integer arrays&nbsp;<code>nums1<\/code>&nbsp;and&nbsp;<code>nums2<\/code>&nbsp;of length&nbsp;<code>n<\/code>.<\/p>\n\n\n\n<p>The&nbsp;<strong>XOR sum<\/strong>&nbsp;of the two integer arrays is&nbsp;<code>(nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1])<\/code>&nbsp;(<strong>0-indexed<\/strong>).<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, the&nbsp;<strong>XOR sum<\/strong>&nbsp;of&nbsp;<code>[1,2,3]<\/code>&nbsp;and&nbsp;<code>[3,2,1]<\/code>&nbsp;is equal to&nbsp;<code>(1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4<\/code>.<\/li><\/ul>\n\n\n\n<p>Rearrange the elements of&nbsp;<code>nums2<\/code>&nbsp;such that the resulting&nbsp;<strong>XOR sum<\/strong>&nbsp;is&nbsp;<strong>minimized<\/strong>.<\/p>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>XOR sum<\/strong>&nbsp;after the rearrangement<\/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> nums1 = [1,2], nums2 = [2,3]\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong> Rearrange <code>nums2<\/code> so that it becomes <code>[3,2]<\/code>.\nThe XOR sum is (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2.<\/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> nums1 = [1,0,3], nums2 = [5,3,4]\n<strong>Output:<\/strong> 8\n<strong>Explanation:<\/strong> Rearrange <code>nums2<\/code> so that it becomes <code>[5,4,3]<\/code>. \nThe XOR sum is (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>n == nums1.length<\/code><\/li><li><code>n == nums2.length<\/code><\/li><li><code>1 &lt;= n &lt;= 14<\/code><\/li><li><code>0 &lt;= nums1[i], nums2[i] &lt;= 10<sup>7<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP \/ Permutation to combination<\/strong><\/h2>\n\n\n\n<p>dp[s] := min xor sum by using a subset of nums2 (presented by a binary string s) xor with nums1[0:|s|].<\/p>\n\n\n\n<p>Time complexity: O(n*2<sup>n<\/sup>)<br>Space complexity: O(2<sup>n<\/sup>)<\/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 Solution {\npublic:\n  int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {\n    const int n = nums1.size();\n    vector<int> dp(1 << n, INT_MAX);\n    dp[0] = 0;\n    for (int s = 0; s < 1 << n; ++s) {\n      int index = __builtin_popcount(s);\n      for (int i = 0; i < n; ++i) {\n        if (s &#038; (1 << i)) continue;\n        dp[s | (1 << i)] = min(dp[s | (1 << i)],\n                               dp[s] + (nums1[index] ^ nums2[i]));\n      }\n    }    \n    return dp.back();\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given two integer arrays&nbsp;nums1&nbsp;and&nbsp;nums2&nbsp;of length&nbsp;n. The&nbsp;XOR sum&nbsp;of the two integer arrays is&nbsp;(nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + &#8230; + (nums1[n -&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[122,18,217,121],"class_list":["post-8509","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-combination","tag-dp","tag-hard","tag-permutation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8509","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=8509"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8509\/revisions"}],"predecessor-version":[{"id":8511,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8509\/revisions\/8511"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8509"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8509"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8509"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}