Problem

You are given an array nums​​​ and an integer k​​​​​. The XOR of a segment [left, right] where left <= right is the XOR of all the elements with indices between left and right, inclusive: nums[left] XOR nums[left+1] XOR ... XOR nums[right].

Return the minimum number of elements to change in the array such that the XOR of all segments of size k​​​​​​ is equal to zero.

Examples

Example 1

1
2
3

Input: nums = [1,2,0,3,0], k = 1
Output: 3
Explanation: Modify the array from [_**1**_ ,_**2**_ ,0,_**3**_ ,0] to from [_**0**_ ,_**0**_ ,0,_**0**_ ,0].

Example 2

1
2
3

Input: nums = [3,4,5,2,1,7,3,4,7], k = 3
Output: 3
Explanation: Modify the array from [3,4,**_5_** ,**_2_** ,**_1_** ,7,3,4,7] to [3,4,**_7_** ,**_3_** ,**_4_** ,7,3,4,7].

Example 3

1
2
3

Input: nums = [1,2,4,1,2,5,1,2,6], k = 3
Output: 3
Explanation: Modify the array from [1,2,**_4,_** 1,2,**_5_** ,1,2,**_6_**] to [1,2,**_3_** ,1,2,**_3_** ,1,2,**_3_**].

Constraints

  • 1 <= k <= nums.length <= 2000
  • ​​​​​​0 <= nums[i] < 210

Solution

Method 1 – Dynamic Programming with Frequency Counting

Intuition

The problem can be viewed as partitioning the array into k groups based on their indices modulo k. For each group, we want to choose values so that the XOR of one value from each group is zero, while minimizing the number of changes. Dynamic programming helps us efficiently compute the minimum changes needed for all possible XOR values.

Approach

  1. Let dp[x] be the minimum number of changes needed so that the XOR of one value from each group is x.
  2. For each group (indexed by i % k):
    • Count the frequency of each value in the group.
    • For each possible XOR value x (0 to 2^8-1):
      • For each value v in the group, update ndp[x] as the minimum of its current value and dp[x ^ v] + (group size - freq[v]).
    • After processing the group, set dp = ndp.
  3. The answer is dp[0] after processing all groups.

Code

 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

class Solution {
public:
    int minChanges(vector<int>& nums, int k) {
        const int MAXX = 1 << 8;
        vector<int> dp(MAXX, 1e9);
        dp[0] = 0;
        int n = nums.size();
        for (int i = 0; i < k; ++i) {
            vector<int> cnt(MAXX, 0);
            int sz = 0;
            for (int j = i; j < n; j += k) {
                cnt[nums[j]]++;
                sz++;
            }
            int mn = *min_element(dp.begin(), dp.end());
            vector<int> ndp(MAXX, mn + sz);
            for (int x = 0; x < MAXX; ++x) {
                for (int v = 0; v < MAXX; ++v) {
                    if (cnt[v]) {
                        ndp[x] = min(ndp[x], dp[x ^ v] + sz - cnt[v]);
                    }
                }
            }
            dp = ndp;
        }
        return dp[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

func minChanges(nums []int, k int) int {
    MAXX := 256
    dp := make([]int, MAXX)
    for i := range dp {
        dp[i] = 1e9
    }
    dp[0] = 0
    n := len(nums)
    for i := 0; i < k; i++ {
        cnt := make([]int, MAXX)
        sz := 0
        for j := i; j < n; j += k {
            cnt[nums[j]]++
            sz++
        }
        mn := 1e9
        for _, v := range dp {
            if v < mn {
                mn = v
            }
        }
        ndp := make([]int, MAXX)
        for x := 0; x < MAXX; x++ {
            ndp[x] = mn + sz
        }
        for x := 0; x < MAXX; x++ {
            for v := 0; v < MAXX; v++ {
                if cnt[v] > 0 {
                    if dp[x^v]+sz-cnt[v] < ndp[x] {
                        ndp[x] = dp[x^v] + sz - cnt[v]
                    }
                }
            }
        }
        dp = ndp
    }
    return dp[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

class Solution {
    public int minChanges(int[] nums, int k) {
        int MAXX = 256;
        int[] dp = new int[MAXX];
        Arrays.fill(dp, 1000000000);
        dp[0] = 0;
        int n = nums.length;
        for (int i = 0; i < k; i++) {
            int[] cnt = new int[MAXX];
            int sz = 0;
            for (int j = i; j < n; j += k) {
                cnt[nums[j]]++;
                sz++;
            }
            int mn = Integer.MAX_VALUE;
            for (int v : dp) mn = Math.min(mn, v);
            int[] ndp = new int[MAXX];
            Arrays.fill(ndp, mn + sz);
            for (int x = 0; x < MAXX; x++) {
                for (int v = 0; v < MAXX; v++) {
                    if (cnt[v] > 0) {
                        ndp[x] = Math.min(ndp[x], dp[x ^ v] + sz - cnt[v]);
                    }
                }
            }
            dp = ndp;
        }
        return dp[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

class Solution {
    fun minChanges(nums: IntArray, k: Int): Int {
        val MAXX = 256
        var dp = IntArray(MAXX) { 1_000_000_000 }
        dp[0] = 0
        val n = nums.size
        for (i in 0 until k) {
            val cnt = IntArray(MAXX)
            var sz = 0
            for (j in i until n step k) {
                cnt[nums[j]]++
                sz++
            }
            val mn = dp.minOrNull() ?: 0
            val ndp = IntArray(MAXX) { mn + sz }
            for (x in 0 until MAXX) {
                for (v in 0 until MAXX) {
                    if (cnt[v] > 0) {
                        ndp[x] = minOf(ndp[x], dp[x xor v] + sz - cnt[v])
                    }
                }
            }
            dp = ndp
        }
        return dp[0]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def minChanges(self, nums: list[int], k: int) -> int:
        MAXX = 256
        dp = [10**9] * MAXX
        dp[0] = 0
        n = len(nums)
        for i in range(k):
            cnt = [0] * MAXX
            sz = 0
            for j in range(i, n, k):
                cnt[nums[j]] += 1
                sz += 1
            mn = min(dp)
            ndp = [mn + sz] * MAXX
            for x in range(MAXX):
                for v in range(MAXX):
                    if cnt[v]:
                        ndp[x] = min(ndp[x], dp[x ^ v] + sz - cnt[v])
            dp = ndp
        return dp[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

impl Solution {
    pub fn min_changes(nums: Vec<i32>, k: i32) -> i32 {
        let maxx = 256;
        let mut dp = vec![1_000_000_000; maxx];
        dp[0] = 0;
        let n = nums.len();
        for i in 0..k as usize {
            let mut cnt = vec![0; maxx];
            let mut sz = 0;
            let mut j = i;
            while j < n {
                cnt[nums[j] as usize] += 1;
                sz += 1;
                j += k as usize;
            }
            let mn = *dp.iter().min().unwrap();
            let mut ndp = vec![mn + sz; maxx];
            for x in 0..maxx {
                for v in 0..maxx {
                    if cnt[v] > 0 {
                        ndp[x] = ndp[x].min(dp[x ^ v] + sz - cnt[v]);
                    }
                }
            }
            dp = ndp;
        }
        dp[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

class Solution {
    minChanges(nums: number[], k: number): number {
        const MAXX = 256;
        let dp = Array(MAXX).fill(1e9);
        dp[0] = 0;
        const n = nums.length;
        for (let i = 0; i < k; i++) {
            const cnt = Array(MAXX).fill(0);
            let sz = 0;
            for (let j = i; j < n; j += k) {
                cnt[nums[j]]++;
                sz++;
            }
            const mn = Math.min(...dp);
            const ndp = Array(MAXX).fill(mn + sz);
            for (let x = 0; x < MAXX; x++) {
                for (let v = 0; v < MAXX; v++) {
                    if (cnt[v]) {
                        ndp[x] = Math.min(ndp[x], dp[x ^ v] + sz - cnt[v]);
                    }
                }
            }
            dp = ndp;
        }
        return dp[0];
    }
}

Complexity

  • ⏰ Time complexity: O(k * 256^2), since for each of the k groups, we process all 256 possible XOR values and for each, all 256 possible group values.
  • 🧺 Space complexity: O(256), as we only store DP arrays of size 256.