Skip to main content

464. Can I Win

medium

Two players alternately pick integers from 1..maxChoosableInteger (no repeats) and add them to a running total; first to push the total at or above the target wins. Bitmask DP over (used numbers) — at most 20 numbers fit cleanly in an int.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

In the "100 game" two players take turns adding, to a running total, any integer from 1 to 10. The player who first causes the running total to reach or exceed 100 wins. What if we change the game so that players cannot re-use integers? For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total >= 100. Given two integers maxChoosableInteger and desiredTotal, return true if the first player to move can force a win, otherwise, return false. Assume both players play optimally.

Constraints

  • 1 <= maxChoosableInteger <= 20
  • 0 <= desiredTotal <= 300

Examples

Example 1

Input
maxChoosableInteger = 10, desiredTotal = 11
Output
false

Explanation: No matter which integer the first player choose, the first player will lose. The first player can choose an integer from 1 up to 10. If the first player choose 1, the second player can only choose integers from 2 up to 10. The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal. Same with other integers chosen by the first player, the second player will always win.

Example 2

Input
maxChoosableInteger = 10, desiredTotal = 0
Output
true

Example 3

Input
maxChoosableInteger = 10, desiredTotal = 1
Output
true

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Early exits: if desiredTotal <= 0 return true; if sum(1..maxChoosableInteger) < desiredTotal return false.

Hint 2

Bitmask state: bit k of mask is 1 iff integer k+1 has been used. Memoize wins(mask, remaining).

Hint 3

Because remaining is determined by mask alone (remaining = desiredTotal - sum of used integers), memoize on mask only.

Hint 4

Current player wins iff there exists an unused i with: (i + 1 >= remaining) OR (recursive call with i toggled returns false for opponent).

Solution approach

Reveal approach

Bitmask DP with memoization on the used-set mask. Early exits: if desiredTotal <= 0 the first player has already won, return true; if sum(1..maxChoosableInteger) < desiredTotal nobody can reach the target, return false. Otherwise define wins(mask, remaining): for each integer i in 1..maxChoosableInteger, if the bit for i is unset in mask, simulate picking it. If i >= remaining, current player wins immediately. Else if wins(mask | bit(i), remaining - i) is false (opponent loses), current player wins. If no choice wins, return false. Memoize on mask alone since remaining is determined by mask. Call wins(0, desiredTotal). Time O(2^M * M) where M = maxChoosableInteger. Listed here for the game/bitmask DP family.

Complexity

Time
O(2^M * M)
Space
O(2^M)

Related patterns

  • dynamic-programming
  • bitmask-dp
  • game-theory
  • memoization

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • LinkedIn

Practice these live with InterviewChamp.AI

Drill Can I Win and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →