1787. Make the XOR of All Segments Equal to Zero

Notes 2020:

Intuition 1: nums[i] == nums[i+c*k] where c is a positive number.

Based on Intuition 1, original problem is converted to:

1. Given k group of numbers, each group may contain some duplications.
1. pick one number out from each group among those k groups such that xor of those picked numbers is 0
- case 2.1: the picked number can be an existing number within the group (i.e., changing all other numbers to this number in the group)
  - number of changes is count[i-1] - freq[i-1][m]
- case 2.2: the picked number was not originally in the group (i.e., every number within the group needs to be changed)
  - number of changes is count[i-1]

dp[i][j] denotes the min number of changes in the first i groups such that the xor of all those numbers is j

for case 2.1, dp[i][j] = min(dp[i][j], count[i-1] - freq[i-1][m] + dp[i-1][j^m]). Note that (j^m) ^ m = j
for case 2.2, numbers in the group can be changed to any number so we choose the one that can get min(dp[i-1])

Loop-i will run k times, loop-j will run 1024 times, and loop-m will run n/k times so T = O(k1024 n/k) = O(n)

class Solution:
    def minChanges(self, nums: List[int], k: int) -> int:
        MAX_NUM = 1024
        
        freq = collections.defaultdict(Counter)
        count = [0] * k
        for i, num in enumerate(nums):
            freq[i%k][num] += 1
            count[i%k] += 1
            
        # dp[i][j] is min number of elements to change such that xor of all previous segments of size k is equal to j
        dp = [[float("inf")] * MAX_NUM for _ in range(k+1)] 
        dp[0][0] = 0
        for i in range(1, k+1):
            # case 1: all numbers in freq[i-1] need to be changed. In this case, it doesn't matter what dp[i-1] can contribute. To minimize the number of changes we need to make, we choose the smallest dp[i-1][j]
            candidate = min(dp[i-1]) + count[i-1]
            for j in range(MAX_NUM):
                for m in freq[i-1]:
                    dp[i][j] = min(dp[i][j], candidate, count[i-1] - freq[i-1][m] + dp[i-1][j^m])
        
        return dp[k][0]

1787. Make the XOR of All Segments Equal to Zero - cocoder39/coco39_LC GitHub Wiki