• + 0 comments

    The game is simple, all you have to do is make the xor of all the piles equal to zero if they are not already. The main thing is finding the algorithm for this.

    Look at the the bitwise xor of all the elements

    For example: piles = [10,4,5,1]

    if I draw its bitwise map then (Symbol "x" equates to 1) :

    10  = > X 0 X 0
    4   = > 0 X 0 0
    5   = > 0 X 0 X
    1   = > 0 0 0 X
    

    Now make their xor equal to zero and using the minimum amount of changes. From here all you need to do is check if there is an requirement of 1 or there is excess of 1 and we need to look column wise for this to solve. If there is excess of 1 then find the row which has the nearest 1 and then shift it's position. If it is excess then you need to shift the excess in front and start with that row.

    (Initial)

    10  = > X 0 X 0
    4   = > 0 X 0 0
    5   = > 0 X 0 X
    1   = > 0 0 0 X
    

    (Step - 1) (We correct for row 1)

    10  = > X 0 X 0
    8   = > X 0 0 0
    5   = > 0 X 0 X
    1   = > 0 0 0 X
    

    (Step - 2)(We correct for row 2)

    12  = > X X 0 0
    8   = > X 0 0 0
    5   = > 0 X 0 X
    1   = > 0 0 0 X
    

    (Step - 3) and (Step - 4) are not necessary to show as they are already corrected.

    Let's take another example for the case of piles = [1,1,1]

    (Initial)

    1 = > 0 X
    1 = > 0 X
    1 = > 0 X
    

    (Step - 1) In this there is an excess of 1 so we shift that one ahead and start with that row again

    1 = > 0 X
    1 = > 0 X
    2 = > X 0
    

    (Step - 2) Now, we need to apply correction to the row that we just shifted.

    1 = > 0 X
    2 = > X 0
    2 = > X 0
    

    (Step - 3) Now first row has been corrected and the second row needs correction. If there is no other way to add an 1 the we introduce the 1 in the last row

    1 = > 0 X
    3 = > X X
    2 = > X 0
    

    Now, you just need to convert the rows to their respective integers and subtract and add the difference in the count and return the count

    For example:

    piles   = [1,1,1]
    ^piles  = [2,3,1]
    total   =  1 + 2 + 0 = > 3
    

    and

    piles   = [10,4,5,1]
    ^piles  = [12,8,5,1]
    total   = 2 + 4 + 0 + 0 = > 6
    

    and

    piles   = [1,3]
    ^piles  = [3,3]
    total   = 2 + 0 = > 2
    

    That is how to solve this question I guess. I will try it.