Problem asked in test. Please help

Hello, this problem was asked in one of my coding tests.

Minimum number of changes in an array to ensure that XOR of all K consecutive elements is zero

1 ≤ k ≤ n ≤ 10^4
0 ≤ A[i] < 1024

We have an array of size N

Now, we want to change the array such that the Bitwise XOR of every K Consecutive elements becomes 0. Find the minimum number of elements we need to change.

Input format: Input consists of 2 arguments, first is vector A and second is K.

Output format: Return a single integer, the minimum number of changes required.

Example: A=[1, 2, 3, 1], K=3; Output = 0.
A=[1, 2, 5] K=3; Output = 1.

1 Like

I am not sure if it is correct or not but here is what i have come up with -

Let’s consider an array A = {a,b,c,d,e,f,g,h,i} and let k be 3 .
Xor of a,b,c = Xor of b,c,d —> (1)
Xor of b,c,d = Xor of c,d,e ---->(2)

As we can see that in equation (1) b,c is constant in both side which means a==b
similarly , from equation (2) c,d is constant in both side which implies b==d .

So, the elements will repeat after the Kth term so, the final array becomes A = {a,b,c,a,b,c,a,b,c} for K=3.

Now you can just check for each element in range (1<= i <=k ) and find the minimum answer .

1 Like

The observation made by you is correct but still calculating answer isn’t that easy as you have described.
You need to do an dp[n][max(A)].
I think this question appeared in codeagon 2020