XORSUB: Editorial with Gaussian Elimination

I would like to explain the Gaussian Elimination method which I have used and got AC in 0.00 :slight_smile: The link to my solution. (sorry for some dubugging statements in it).

  1. 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[].
  2. 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.
  3. Now will have a x[] array which will
    be of size = no. of bit the maximum
    of array is
  4. 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.
  5. 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][0]

x[] is modified_array[]

3 Likes

A small proof would be better like why this works.