Bitwise Blend Practice Coding Problem

editorial
, ,
1

link: Bitwise Blend Practice Coding Problem

Observations:

The first parity condition says
for every adjacent pair x and y:

parity(x&y) != parity(x|y)

We notice that this is possible if and only if it is an (odd,even) pair or (even,odd) pair.

And since it’s valid for all the adjacent pairs in the array, so for the array to be tasty, it should have one of the following form:

Form 1) odd, even, odd, even, odd…
Form 2) even, odd, even, odd, even…

Now the operations we are allowed to perform is to chose any x and y, and replace x by x^y.

1^1 = 0
0^1 = 1

So we notice that:
An odd x can by changed to even by choosing an odd y.
an even x can be changed to odd by choosing an odd y.

Hence the y to be chosen is always odd.

Which means:

  1. the edge cases is when no odd number exists in the array, and hence the array is not updatable.
    print(-1)

  2. Now we check which form mentioned above is easy to attain.

Example,
For 1, 2, 4, 6, the right form is odd,even,odd even. Since only 4 needs to be updated.
For 8, 5, 3, 5, 6, 7, the right form is even,odd,even,odd… Since only 3 needs to be updated.

To check, just make [1,0,1,0,1,0…] and [0,1,0,1,0,1…] And make a parity array or the given array.

Check which form matches better with this parity array.

Print the number of non-matching indexes of this better form.

Then chose y sucht that it is in the right form and it is an odd number as said before.

for all x, the non-matching indexes with this better-form:

print(x,y)