Help me in solving BOX95 problem

help
,
1

My issue

I did not understand the xor and the or relation given in the question. how did it tell that odd number of highest bits are present?

Problem Link: BOX95 Problem - CodeChef

2

Well you can easily observe this fact:
Let’s Proove this by contradiction->
Assume the highest bit B appears even number of times ~ This means that when XOR of entire array is taken this bit will be unset in the final XOR value.
Whereas when we take OR of the entire array that means this bit will still remain set no matter if it occurs even number of times.
If this occurs this would mean that highest bit will be absent in XOR value of the array and present in OR value of the array.
This would not satisfy the equality 2 * (XOR(Ai)) >= (OR(Ai)) for i : [1, N]
Hence by contradiction the number of times the highest bit occur has to be ODD.

1 Like