Ctrl K

Shared Pool Race to a Goal

Medium
Two players play the following game. There are cards on the table numbered 1 to top, one of each. Players take turns: on a turn you pick any remaining card and add its number to a shared running total (which starts at 0). A card that has been taken is out of the game. Whoever makes the total reach goal or more first wins. Both players play perfectly. Return True if the first player can force a win, and False otherwise. If the cards run out before the total reaches goal, nobody wins, which also counts as False. If goal is 0, the first player is considered the winner right away.
Example 1
top=5, goal=6 → False

Whatever the first player takes (1 to 5), the second player can grab a free number that brings the total to 6 or more. The first player loses.

Example 2
top=6, goal=6 → True

The first player takes 6 right away and wins.

Example 3
top=4, goal=11 → False

All the numbers add up to 1 + 2 + 3 + 4 = 10 < 11, so nobody ever reaches the goal and the first player does not win.

Constraints
  • 1 ≤ top ≤ 20
  • 0 ≤ goal ≤ 300
Have you seen this problem in a real interview?
Solved by0
Tried by0
Submissions0
Acceptance—
Topics
Similar problemsCheapest Basket with Bundles MediumGroups With Equal Sums MediumTake From Any Pile MediumFewest Lines Through the Dots MediumProducts Free of Squares Medium
loading Python…
Input
top=5, goal=6
Expected
False

Run checks the first 3 tests in your browser. Submit checks all 78 tests on the server, hidden ones included.