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.
2 Likes
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