Problem asked in Media.net 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 .
So,
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