Minimum XOR Sum of Two Arrays LeetCode solution in Java

1
class Solution {
2
  Integer[][] cache;
3

4
  public int minimumXORSum(int[] nums1, int[] nums2) {
5
    int n = nums1.length;
6

7
    cache = new Integer[n][1 << n];
8

9
    return getMinXorSum(0, 0, nums1, nums2);
10
  }
11

12
  private int getMinXorSum(int index, int mask, int[] nums1, int[] nums2) {
13
    if (index == nums1.length) return 0;
14

15
    // retrieve from cache
16
    if (cache[index][mask] != null) return cache[index][mask];
17

18
    // find minimum
19
    int minXorSum = Integer.MAX_VALUE;
20

21
    for (int i = 0; i < nums2.length; i++) {
22
      if ((mask >> i & 1) == 1) continue;
23

24
      int xorSum =
25
          (nums1[index] ^ nums2[i]) + getMinXorSum(index + 1, mask | (1 << i), nums1, nums2);
26

27
      // update minimum xor sum
28
      minXorSum = Math.min(xorSum, minXorSum);
29
    }
30

31
    // store in cache
32
    cache[index][mask] = minXorSum;
33

34
    return minXorSum;
35
  }
36
}