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

1
class Solution {
2
 public:
3
  int minChanges(vector<int> &nums, int k) {
4
    const auto n = nums.size();
5
    const int limit =
6
        1 << static_cast<int>(ceil(log2(*max_element(nums.cbegin(), nums.cend()) + 1)));
7

8
    vector<unordered_map<int, int>> freq(k);
9
    for (int i = 0; i != n; ++i) {
10
      ++freq[i % k][nums[i]];
11
    }
12

13
    vector<int> dp(limit);
14
    vector<int> tmpdp(limit);
15
    int last_min = numeric_limits<int>::max();
16

17
    for (int j = 0; j != limit; ++j) {
18
      dp[j] = n / k + (n % k > 0) - freq[0][j];
19
      last_min = min(last_min, dp[j]);
20
    }
21

22
    for (int i = 1; i != k; ++i) {
23
      int cnt = n / k + (n % k > i);
24
      int new_min = numeric_limits<int>::max();
25
      for (int j = 0; j != limit; ++j) {
26
        int mi = numeric_limits<int>::max();
27
        for (auto &[v, f] : freq[i]) {
28
          mi = min(mi, dp[j ^ v] - f);
29
        }
30
        mi = min(mi, last_min);
31

32
        mi += cnt;
33
        new_min = min(new_min, mi);
34
        tmpdp[j] = mi;
35
      }
36
      last_min = new_min;
37
      swap(tmpdp, dp);
38
    }
39

40
    return dp[0];
41
  }
42
};