Make the XOR of All Segments Equal to Zero LeetCode solution in Java

1
class Solution {
2
  public int minChanges(int[] nums, int k) {
3
    // solution (sequence) is uniquely defined by the first k elements, because a[i] == a[i+k] ==
4
    // a[i+2k] == ... for any offset i
5
    int v = 1 << 10;
6
    // best[pattern] is the highest number of relevant (ie. those with offsets between 0 and i)
7
    // elements in nums
8
    // that can be left unchanged to achieve a[0] ^ a[1] ^ ... ^ a[i] == pattern
9
    int[] best = new int[v];
10
    // iterate over over each offset i of the solution
11
    for (int i = 0; i < k; i++) {
12
      // find frequencies of distinct element values present in the subsequence with offset i
13
      Map<Integer, Integer> n2c = new HashMap<Integer, Integer>();
14
      for (int p = i; p < nums.length; p += k) {
15
        n2c.put(nums[p], 1 + n2c.getOrDefault(nums[p], 0));
16
      }
17
      // treat initial subsequence (i = 0) correctly
18
      if (i == 0) {
19
        for (int vv : n2c.keySet()) {
20
          best[vv] = n2c.get(vv);
21
        }
22
        continue;
23
      }
24
      int[] next = new int[v];
25
      int max = 0;
26
      for (int j : best) max = Math.max(max, j);
27
      // elements previously unchanged (ie. from subsequences with offsets 0, 1, 2, .., i-1) can be
28
      // carried to the current offset i
29
      // max of all best[] is used
30
      for (int j = 0; j < v; j++) next[j] = max;
31
      // for elements present in the subsequnce with offset i next[] can be improved accordingly
32
      for (int vv : n2c.keySet()) {
33
        int cnt = n2c.get(vv);
34
        for (int j = 0; j < v; j++) {
35
          next[j ^ vv] = Math.max(next[j ^ vv], best[j] + cnt);
36
        }
37
      }
38
      best = next;
39
    }
40
    // solution is for pattern == 0, hence best[0]. Report minimum number of elements to change
41
    // rather than maximum that can be left unchanged.
42
    return nums.length - best[0];
43
  }
44
}