1199 - Partitioning Game

Problem Link 
Concept:
Grundy’s game:
Sometimes a move in the game divides the game into sub-games that are independent
of each other. In this case, the Grundy number of the game is
                                                 mex({g₁, g₂,..., g_n}),
where n is the number of possible moves and
                                        gk = a_k,1 xor a_k,2 xor ... xor a_k,m,
where move k generates sub-games with Grundy numbers a_k,1,a_k,2,...,a_k,m.
An example of such a game is Grundy’s game. Initially, there is a single
heap that contains n sticks. On each turn, the player chooses a heap and divides
it into two nonempty heaps such that the heaps are of different size. The player
who makes the last move wins the game.
Let f (n) be the Grundy number of a heap that contains n sticks. The Grundy
number can be calculated by going through all ways to divide the heap into two
heaps. For example, when n = 8, the possibilities are 1+7, 2+6 and 3+5, so
                         f (8) = mex({ f (1) xor f (7), f (2) xor f (6), f (3) xor f (5)}).
In this game, the value of f (n) is based on the values of f (1),..., f (n-1). The
base cases are f (1) xor f (2) = 0, because it is not possible to divide the heaps of 1
and 2 sticks. The first Grundy numbers are:

f (1) = 0
f (2) = 0
f (3) = 1
f (4) = 0
f (5) = 2
f (6) = 1
f (7) = 0
f (8) = 2

The Grundy number for n = 8 is 2, so it is possible to win the game. The winning
move is to create heaps 1+7, because f (1) xor f (7) = 0.

Solution: