<p>You are given an array <code>nums</code>​​​ and an integer <code>k</code>​​​​​. The <font face="monospace">XOR</font> of a segment <code>[left, right]</code> where <code>left &lt;= right</code> is the <code>XOR</code> of all the elements with indices between <code>left</code> and <code>right</code>, inclusive: <code>nums[left] XOR nums[left+1] XOR ... XOR nums[right]</code>.</p>

<p>Return <em>the minimum number of elements to change in the array </em>such that the <code>XOR</code> of all segments of size <code>k</code>​​​​​​ is equal to zero.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,0,3,0], k = 1
<strong>Output:</strong> 3
<strong>Explanation: </strong>Modify the array from [<u><strong>1</strong></u>,<u><strong>2</strong></u>,0,<u><strong>3</strong></u>,0] to from [<u><strong>0</strong></u>,<u><strong>0</strong></u>,0,<u><strong>0</strong></u>,0].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,4,5,2,1,7,3,4,7], k = 3
<strong>Output:</strong> 3
<strong>Explanation: </strong>Modify the array from [3,4,<strong><u>5</u></strong>,<strong><u>2</u></strong>,<strong><u>1</u></strong>,7,3,4,7] to [3,4,<strong><u>7</u></strong>,<strong><u>3</u></strong>,<strong><u>4</u></strong>,7,3,4,7].
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,4,1,2,5,1,2,6], k = 3
<strong>Output:</strong> 3
<strong>Explanation: </strong>Modify the array from [1,2,<strong><u>4,</u></strong>1,2,<strong><u>5</u></strong>,1,2,<strong><u>6</u></strong>] to [1,2,<strong><u>3</u></strong>,1,2,<strong><u>3</u></strong>,1,2,<strong><u>3</u></strong>].</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= nums.length &lt;= 2000</code></li>
	<li><code>​​​​​​0 &lt;= nums[i] &lt; 2<sup>10</sup></code></li>
</ul>

class Solution:
    def minChanges(self, nums: List[int], k: int) -> int:
        # second pass, let's try this again

        # wlog suppose we've fixed some interval v1..vk | x1..k = 0
        # then the next window lacks v1, has v{k+1}
        # x2..k+1 = x1..k ^ x1 ^ x{k+1} = 0 ^ x1 ^ x{k+1} = x1 ^ x{k+1}
        #
        #    conclusion: nums[i] == nums[i+k] for all i after we make the changes
        #
        # every "residue group," with indices mod k equal to the same value 0..k-1,
        # must be set to the same number

        # furthermore: there are many ways to change these values to achieve xor equal to zero
        #
        # DP strategy: we want ways to set 0..k-1 xor to 0
        #
        # Not totally obvious, but somewhat straightforward:
        #   > we can set indices in residue group k-1 (henceforth "group k") to 0, and the rest to 0
        #   > or set group k-1 to 1, and 0..k-2 to have xor 1
        #   > ...
        #   > pick the one with min cost

        # in general: we want cost[i][x] where
        #    > i means we're setting groups 0..i <= k-1
        #    > and x is the xor value we get

        # to get cost[i][x], there are many ways to make 0..i have xor x:
        #    pick group i to have xor 0, prior group xor x: size[i] - freq[i][0] + cost[i-1][0]
        #                             1,               x^1: size[i] - freq[i][1] + cost[i-1][x^1]
        #
        #    so we get min_v ( size[i] - freq[i][v] + cost[i-1][x ^ v] )
        #
        # Doing this literally: each value is less than 2**10 so there are 10 bits each
        # the xors can be anything, so we need to consider all 2**10 combos
        #
        # So for each x in 2**10, iterate over all v in 2**10 values
        # (we'll call this M for "max")
        #
        # That's M**2 * k operations, roughly k/4 * 1e6 ops. For k order 10+ we'll start
        # getting TLE
        #
        # VERY subtle observation: there are n values and k groups
        # so there are at most n/k distinct values per group
        #
        # for values not in group i, min_v (size[i] - freq[i][v] + cost[i-1][x ^ v])
        # simplifies to size[i] + min_v (cost[i-1][x ^ v])
        #    > size[i] is fixed so it can be brought outside the max
        #    > min_v (...) is the min over all possible values
        #        > min_v f(x ^ v) == min_v f(v) !!!
        #        > that's because we try all bit combinations
        #        > the x ^ v toggles the bits of v in x
        #        > which doesn't change the fact that we traverse all indices - it only
        #        > changes the ORDER we traverse... which doesn't affect the min!!
        #  So for values with freq[i][v] == 0, the answer is size[i] + min(cost[i-1][:])
        #
        # For the n/k values with nonzero freq, we need to do the loop. The loop will be
        # lower when we include the term. So the answer is min over keys with nonzero freq,
        # and the min with the "fallback" min (what vortrubac calls the "wild cost"?)
        #
        # So now for each k:
        #    for each x:
        #        find min of size[i] - freq[i][v] + cost[i-1][x^v] for all v with nonzero freq, n/k
        #        take min with min of size[i] + cost[i-1][:] in O(1)
        #
        # so total cost is k * M * (n/k + 1) = k*M + n*M
        #   k < n so we get order n*M = 1024 * n
        #  which is up to about a million in this problem. Neat

        # space-saving version: we only need the answers for cost[i-1][*]

        M = 1024
        N = len(nums)

        freqs = Counter(nums[i] for i in range(0, N, k))
        size = sum(freqs.values())
        prev_cost = [size - freqs.get(x, 0) for x in range(M)]
        curr_cost = [0]*M
        for i in range(1, k):
            min_prev = min(prev_cost)
            freqs = Counter(nums[j] for j in range(i, N, k))
            size = sum(freqs.values())

            # min if we take zero frequencies is size[i] + min(cost[i-1][:]) (see above)
            zeroFreq = min_prev + size
            for x in range(M if i < k-1 else 1):
                # min_v (size[i] - freq[i][v] + cost[i-1][x^v])
                #     size[i] is pulled out, freq is the dict value
                nonzeroFreq = size + min(prev_cost[x^v] - f for v, f in freqs.items())
                curr_cost[x] = min(nonzeroFreq, zeroFreq)

            prev_cost, curr_cost = curr_cost, prev_cost

        return prev_cost[0] # cost[k-1][0], i.e. set values in all groups 0..k-1 to have xor x==0
3648