Grundy Number (Sprague–Grundy)

Difficulty: Hard · Topic: Game theory

For an impartial game, the Grundy number of a position is the mex (minimum excludant — the smallest non-negative integer not among) the Grundy numbers of the positions reachable in one move. Given n and the allowed moves, return the Grundy number of position n. A position is losing iff its Grundy number is 0; for a sum of independent games, XOR their Grundy numbers (Sprague–Grundy).

Examples

grundy_number(3, [1,2])
→ 0

Grundy cycles 0,1,2,0,… so g[3]=0 (losing).

grundy_number(5, [1,2])
→ 2

Target complexity: time O(n·k), space O(n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.