Subtraction Game

Difficulty: Medium · Topic: Game theory

Starting from n stones, players alternate removing a number of stones in the set moves; the last to move wins. Return True if the first player wins. A position is Winning if some move leads to a Losing position, and 0 (no move available) is Losing.

Examples

can_win_subtraction(4, [1,2])
→ true

can_win_subtraction(3, [1,2])
→ false

From 3 you can only reach 1 or 2, both Winning.

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.