I would like to explain the Gaussian Elimination method which I have used and got AC in 0.00 The link to my solution. (sorry for some dubugging statements in it).
- The idea here is to choose a no.
which has MSB with maximum value.
With a little thinking, we will get
the max(array) will have this
feature. Say, maximum of array is a
k-bit no. and that no. is M. Now,
there can be multiple no.s which are
k-bit no.s and have the same
highest-value bit as ‘1’. So in that
case we will EX-OR each of them with
the M and put them again input array
(ideally, we can choose any one of
those k-bit no.s as M and put others
in array after ex-oring with it). At
the same time we will keep the no. M
in some other array say x.
- We will keep doing step 1 until we
get 0 as maximum in the array i.e.
this loop will run for iterations =
no. of bit the maximum of array is.
- Now will have a x array which will
be of size = no. of bit the maximum
of array is
- Now we will initialize the answer
variable to given K (because we want
it compulsorily) and loop for each
value in array x, if value of
answer variable is going to increase
with the inclusion of ith element,
we will update the answer variable
with the new value as answer^x[i],
else we will keep it as is.
- Finally returning the value of
answer solves our problem.
About my solution:
Bucket[i] contains all i-bit no.s
the M chosen is first element of bucket i.e. Bucket[i]
x is modified_array