Skip to content

1787. Make the XOR of All Segments Equal to Zero 👍

  • Time: $O(kn \cdot n/k) = O(n^2)$
  • Space: $O(nk)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
 public:
  int minChanges(vector<int>& nums, int k) {
    constexpr int kMax = 1024;
    const int n = nums.size();
    // counts[i] := the counter that maps at the i-th position
    vector<unordered_map<int, int>> counts(k);
    // dp[i][j] := the minimum number of elements to change s.t. XOR(nums[i..k -
    // 1]) is j
    vector<vector<int>> dp(k, vector<int>(kMax, n));

    for (int i = 0; i < n; ++i)
      ++counts[i % k][nums[i]];

    auto countAt = [n, k](int i) -> int { return n / k + (n % k > i ? 1 : 0); };

    // Initialize the DP array.
    for (int j = 0; j < kMax; ++j)
      dp[k - 1][j] =
          countAt(k - 1) - (counts[k - 1].contains(j) ? counts[k - 1][j] : 0);

    for (int i = k - 2; i >= 0; --i) {
      // The worst-case scenario is changing all the i-th position numbers to a
      // non-existent value in the current bucket.
      const int changeAll = countAt(i) + ranges::min(dp[i + 1]);
      for (int j = 0; j < kMax; ++j) {
        dp[i][j] = changeAll;
        for (const auto& [num, freq] : counts[i]) {
          // the cost to change every number in the i-th position to `num`
          const int cost = countAt(i) - freq;
          dp[i][j] = min(dp[i][j], dp[i + 1][j ^ num] + cost);
        }
      }
    }

    return dp[0][0];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
  public int minChanges(int[] nums, int k) {
    final int kMax = 1024;
    final int n = nums.length;
    // counts[i] := the counter that maps at the i-th position
    Map<Integer, Integer>[] counts = new Map[k];
    // dp[i][j] := the minimum number of elements to change s.t. XOR(nums[i..k - 1]) is j
    int[][] dp = new int[k][kMax];

    for (int i = 0; i < k; ++i)
      counts[i] = new HashMap<>();

    for (int i = 0; i < n; ++i)
      counts[i % k].merge(nums[i], 1, Integer::sum);

    Arrays.stream(dp).forEach(A -> Arrays.fill(A, n));

    // Initialize the DP array.
    for (int j = 0; j < kMax; ++j)
      dp[k - 1][j] = countAt(n, k, k - 1) - counts[k - 1].getOrDefault(j, 0);

    for (int i = k - 2; i >= 0; --i) {
      // The worst-case scenario is changing all the i-th position numbers to a
      // non-existent value in the current bucket.
      final int changeAll = countAt(n, k, i) + Arrays.stream(dp[i + 1]).min().getAsInt();
      for (int j = 0; j < kMax; ++j) {
        dp[i][j] = changeAll;
        for (Map.Entry<Integer, Integer> entry : counts[i].entrySet()) {
          final int num = entry.getKey();
          final int freq = entry.getValue();
          // the cost to change every number in the i-th position to `num`
          final int cost = countAt(n, k, i) - freq;
          dp[i][j] = Math.min(dp[i][j], dp[i + 1][j ^ num] + cost);
        }
      }
    }

    return dp[0][0];
  }

  private int countAt(int n, int k, int i) {
    return n / k + (n % k > i ? 1 : 0);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
  def minChanges(self, nums: list[int], k: int) -> int:
    kMax = 1024
    n = len(nums)
    # counts[i] := the counter that maps at the i-th position
    counts = [collections.Counter() for _ in range(k)]
    # dp[i][j] := the minimum number of elements to change s.t. XOR(nums[i..k - 1]) is j
    dp = [[n] * kMax for _ in range(k)]

    for i, num in enumerate(nums):
      counts[i % k][num] += 1

    def countAt(i: int) -> int:
      return n // k + (1 if n % k > i else 0)

    # Initialize the DP array.
    for j in range(kMax):
      dp[k - 1][j] = countAt(k - 1) - counts[k - 1][j]

    for i in range(k - 2, -1, -1):
      # The worst-case scenario is changing all the i-th position numbers to a
      # non-existent value in the current bucket.
      changeAll = countAt(i) + min(dp[i + 1])
      for j in range(kMax):
        dp[i][j] = changeAll
        for num, freq in counts[i].items():
          # the cost to change every number in the i-th position to `num`
          cost = countAt(i) - freq
          dp[i][j] = min(dp[i][j], dp[i + 1][j ^ num] + cost)

    return dp[0][0]