Pocket Gems Interview Question: You and the interviewer play ... | Glassdoor

## Interview Question

Software Engineer Interview San Francisco, CA

# You and the interviewer play a game. There are piles of

stones on a table, each with a different number of stones. On your turn, you can take from the table any positive number of stones from any single pile. The person who takes the last stone wins. What's your move?

1

Suppose We have 3 piles
Case 1: When 0 stones left implies (Loosing Postion 'L')
XOR of non of stones in piles is 0^0^0 =0
Case 2: When 1 stone remains in only one pile and rest piles are empty(Winning Pos W)
XOR of stones 1^0^0=1

So in-general if we play first we should always leave that no.of stones is pile such that XOR of remaining stones is that pile with other piles is 0.

Pragnya Sagar Choudhury on Aug 15, 2012
1

Suppose We have 3 piles
Case 1: When 0 stones left implies (Loosing Postion 'L')
XOR of non of stones in piles is 0^0^0 =0
Case 2: When 1 stone remains in only one pile and rest piles are empty(Winning Pos W)
XOR of stones 1^0^0=1

So in-general if we play first we should always leave that no.of stones is pile such that XOR of remaining stones is that pile with other piles is 0.

Pragnya Sagar Choudhury on Aug 15, 2012
0

You want to make sure that all piles have an even number of stones: the XOR answer works only assuming that the amount in each pile is the same.

Anonymous on Sep 3, 2012
2

This problem is well explained in this video