This question was asked in placement exam of a Company. I was not able to understand this problem.
CLick here to See the question
The first line of input contains N which is number of jugs and next line contains N integers representing number of balls in the jug.
Input:
1
10
Output:
10
Please, someone help me to understand this problem, and if possible suggest a solution as well.
I suspect the solution is take the xor of all the numbers they give you. If the result is 0 there is no solution so return -1. Otherwise return the result.
My reasoning is as follows. If we ignore the first 50 steps where we are adding jugs with balls in them the problem is the standard Nim game and it is a standard result that with optimal the first player wins if the xor of the number of balls in each pile is not zero and the second player wins if the xor is zero. So we want to leave the first 50 moves in a state where the xor is non zero.
Now let's assume we are in one of those first 50 moves and the xor is not equal to zero. Then we can make it zero by adding a jug with the same number of balls as this xor value. Then whatever jug the opponent adds will make the xor non zero. We go to the jug he just added and remove all the balls. The xor is now zero again. Then second player removes some balls and the xor is non zero again. Then we are on the next turn and can repeat the process.
Now if we are in one of the first 50 moves and the xor is equal to zero the second player can send us back to a state where the xor is zero. The strategy will be slightly different. When we add a jug he will follow by adding a jug with the same number of balls making the xor zero. Then when we remove balls he will use the nim strategy to make the xor zero again. So we lose in this case.
This means we always want to start each turn in a state where the xor is not zero and only way to guarantee this is by adding a jug with the number of balls equal to the xor of the starting state on the first turn. If the xor of the first state is zero we can't do this and lose automatically.
In a standard NIM game we can take maximum 3 balls, but there is nothing mentioned in the problem about maximum withdrawl.
I saw this video to know about NIM
I think that is standard in terms of how people play it. When I wrote standard Nim game I was referring to a more general version where any finite number of balls and jugs are allowed and in a turn you can remove any non zero number of balls from a jug. This is standard in the competitive program context. The mathematical theory on this general version exactly as I described.