This article has participated in the weekend study program, click the link to see the details:Juejin. Cn/post / 696572…

The title

You are given two integer arrays nums1 and nums2, both of length N.

The sum of the XOR values of the two arrays is (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) +… + (nums1[n-1] XOR nums2[n-1]) (subscripts start from 0).

For example, the sum of the XOR values of [1,2,3] and [3,2,1] equals (1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4. Rearrange the elements in nums2 to minimize the sum of xor values.

Return the sum of the rearranged xOR values.

 

Example 1:

Input: nums1 = [1,2], nums2 = [2,3] output: 2 explanation: rearrange nums2 to get [3,2]. The sum of XOR values is (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2.Copy the code

Example 2:

Input: nums1 = [1,0,3], nums2 = [5,3,4] output: 8 explanation: rearrange nums2 to get [5,4,3]. The sum of XOR values is (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8.Copy the code

Their thinking

Given that n is the length of the array, this problem can be regarded as the first C digits of NUMs1. Find c digits in nums2 and make them correspond one by one to minimize the xOR and sum. Therefore, we can use the binary number of n bits to represent the different value states of NUMs2, and the JTH bit is 1 to indicate that nums2[j] has been selected.

  • For example, nums1 = [1,2], nums2 = [2,3]
  • 01 indicates that NUMs2 [1]=3 has been selected to form an xor sum with the previous nums1 digit, and dp[01] represents the minimum xor sum in this case
  • 10 indicates that nums2[0]=2 has been selected to form an xor sum with the previous nums1 digit

So DP [11] should be migrated from either DP [01] or DP [10], and the newly generated xOR value should be added

State transition

Find the previous state of the current state and move it

  1. Iterate over each element of NUMs2
  2. (1<<j)&i>0Represents that nums2[j] has been selected in the current state, so we deselect this selection (zero this position), which is one of the states from the previous stepdp[(1<<j)^i]
		for j := 0; j < n; j++ {
			if (1<<j)&i>0{
				val:=dp[(1<<j)^i]+(nums1[cnt(i)-1]^nums2[j])
				if val<dp[i]{
					dp[i]=val
				}
			}

		}
Copy the code

code

func minimumXORSum(nums1 []int, nums2 []int) (res int){

	n:=len(nums1)
	cnt := func(cur int) (res int) {
        
		for k := 0; k < 31; k++ {
			res+=1&cur
            cur>>=1
		}
		return
	}

	mask:=1<<n
	dp := make([]int, mask)
	for i := 1; i < mask; i++{
		dp[i]=2e9
	}
	for i := 1; i < mask; i++ {
		for j := 0; j < n; j++ {
			if (1<<j)&i>0{
				val:=dp[(1<<j)^i]+(nums1[cnt(i)- 1]^nums2[j])
				if val<dp[i]{
					dp[i]=val
				}
			}

		}
	}
	return dp[mask- 1]}Copy the code