You are given two integer arrays nums1
and nums2
of length n
.
The XOR sum of the two integer arrays is (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1])
(0-indexed).
- For example, the XOR sum of
[1,2,3]
and[3,2,1]
is equal to(1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4
.
Rearrange the elements of nums2
such that the resulting XOR sum is minimized.
Return the XOR sum after the rearrangement.
Example 1:
Input: nums1 = [1,2], nums2 = [2,3] Output: 2 Explanation: Rearrangenums2
so that it becomes[3,2]
. The XOR sum is (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2.
Example 2:
Input: nums1 = [1,0,3], nums2 = [5,3,4] Output: 8 Explanation: Rearrangenums2
so that it becomes[5,4,3]
. The XOR sum is (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8.
Constraints:
n == nums1.length
n == nums2.length
1 <= n <= 14
0 <= nums1[i], nums2[i] <= 107
Solution: DP / Permutation to combination
dp[s] := min xor sum by using a subset of nums2 (presented by a binary string s) xor with nums1[0:|s|].
Time complexity: O(n*2n)
Space complexity: O(2n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// Author: Huahua class Solution { public: int minimumXORSum(vector<int>& nums1, vector<int>& nums2) { const int n = nums1.size(); vector<int> dp(1 << n, INT_MAX); dp[0] = 0; for (int s = 0; s < 1 << n; ++s) { int index = __builtin_popcount(s); for (int i = 0; i < n; ++i) { if (s & (1 << i)) continue; dp[s | (1 << i)] = min(dp[s | (1 << i)], dp[s] + (nums1[index] ^ nums2[i])); } } return dp.back(); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment