Minimum changes to make XOR of all segments of a fixed length zero

Problem Statement⌗

Given an array $A$ of length $N$ and an integer $K$, find minimum number of elements to change in the array such that xor of all segments of size $K$ becomes zero.

where $1 \leq K \leq N \leq 2000$ and $0 \leq A_i \leq 1024$

As the window of size $K$ moves one step from first $K$ elements it leaves behind the first element and includes $K+1_{th}$ element. More formally

$$A_1 \oplus A_2 \oplus A_3 \oplus \cdots \oplus A_K = A_2 \oplus A_3 \oplus A_4 \oplus \cdots \oplus A_{K+1}$$

Therefore, all numbers which are distance $K$ apart in the array must be equal.

$$A_{i+bK} = const$$

So we can make groups of numbers and operate on those groups, as to get the end result every number in a group must be same. If a number is at position $i$ then it belongs to the group categorized by $i \% K$.

As an example if $K = 2$ then there will be two buckets to categorize all the numbers in. All numbers at odd positions in the array will belong to bucket $1$ and even positioned numbers will fall in bucket $0$.

At this step we have positions grouped together according to the remainder they give when divided by $K$, now we have to assign a number to every group such that xor of every subarray of length $K$ is zero.

What will be the cost of assigning number $X$ to all the positions in a group $G$?⌗

If total positions in group $G$ are $tot[G]$ and $cnt[G][X]$ is count of $X$ in group $G$. Then cost of assigning $X$ to group $G$ is equal to the numbers which are not equal to $X$ in group $G$, given by $$tot[G]-cnt[G][X]$$

If you write a naïve solution that tries every number in the range $[0, 1024]$ for every group and then checks if condition is met at the end. Then it will not scale for more than 2 groups i.e. $K>2$ as it is of order of $1024^K$. Even sample cases have $K>2$ for two cases.

Slower DP solution⌗

Let $dp[i][xr]$ be the minimum changes to make in first $i$ groups such that xor of every subarray of length $i+1$ is $xr$ not considering the numbers in groups $i+1$ to $k-1$.

If we are considering a number $num$ to be the value of group $i$ then

$$dp[i][xr] = min ( \space dp[i][xr] \space, \space dp[i-1][xr \oplus num] \space + \space cost \space of \space assigning \space num)$$

or, $$dp[i][xr] = min(\space dp[i][xr] \space, \space dp[i-1][xr \oplus num] \space + \space tot[i] - \space cnt[i][num])$$

Now we can try every possible number for every group in a faster way and the final answer will be $dp[K-1][0]$

for(int i=0;i<K;i++){
	for(int xr=0;xr<1024;xr++){
		for(int num=0;num<1024;num++){
			if(i==0)
				dp[i][xr]=tot[i]-cnt[i][xr];
			else
				dp[i][xr]=min(dp[i][xr], dp[i-1][xr^num]+tot[i]-cnt[i][num]);
		}
	}
}

cout<<dp[K-1][0]<<"\n";

Why is this slow ? It’s complexity is $O(K*2^{20})$ which won’t pass if $K \geq 500$ or some equivalent metric.

Faster DP solution⌗

One observation is $cnt[G][num] = 0$ for some number $num$ then its cost is $tot[G]$. Therefore we can modify the innermost loop to check only for the numbers that exist in a particular group so it runs $\lceil \frac{N}K \rceil$ times for every $xr$ , and check for all other numbers in constant time.

It brings down the complexity to $O(N*1024)$ as every existent position will be used once for every value of $xr$.

Another way to understand is that outer loop runs $K$ times, inner loop $1024$ times and innermost loop runs for $\lceil \frac{N}K \rceil$ times.

How to calculate dp for all the numbers that are not present in the array?

Only task remaining is to take into account all the numbers that are not present in a group, and calculation for all of them can be done at once.

Key thing to notice is that for every $xr$ we should consider only one such number that is not present in the group, as it doesn’t affect the cost which is always $tot[G]$, but allows us to choose the minimum value for $dp[i-1][xr \oplus num]$.

As we don’t know what $num$ is beforehand (and we don’t need to), just take the minimum value of $dp[i-1][for \space any \space xr]$ and call it $lastMinimum$.

So, best value of $dp[i][xr]$ for all other numbers not in the group will be

$$lastMinimum + tot[G]$$

In this code $group[i]$ is the set of numbers in group $i$.

int lastMinimum=0,tillnow=K;
for(int i=0;i<K;i++){
	tillnow=n; //to update lastminimum

	for(int xr=0;xr<1024;xr++){

		for(int num:group[i]){
			if(i==0)
				dp[i][xr]=tot[i]-cnt[i][xr];
			else
				dp[i][xr]=min(dp[i][xr],dp[i-1][xr^num]+tot[i]-cnt[i][xr]);

		}

		//for all numbers that are not in current group
		dp[i][xr]=min(dp[i][xr],lastMinimum+tot[i]);
		
		tillnow=min(tillnow,dp[i][xr]);
	}
	
	lastMinimum=tillnow;
}

cout<<dp[K-1][0]<<"\n";

You can practice this problem here on leetcode.

Similar problems

• XORGON - Codechef
• 995. - Leetcode