Can I Win

MediumDynamic Programmingbitmask dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Two players share a pool of the integers 1 through maxChoosableInteger. They alternate turns; on each turn a player removes one unused integer from the pool and adds it to a running total that starts at 0. The first player whose move makes the running total **reach or exceed** desiredTotal wins. Numbers are never reused. Return true if the first player can force a win when both players play optimally, otherwise false. Special cases: if desiredTotal <= 0 the first player wins immediately (true). If the sum of all integers in the pool is less than desiredTotal, nobody can ever win, so return false.

Examples

Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false
Whatever the first player picks, the second player can take a number that pushes the total to at least 11.
Input: maxChoosableInteger = 10, desiredTotal = 0
Output: true
The target is already met.
Input: maxChoosableInteger = 10, desiredTotal = 1
Output: true
Any pick reaches 1.

Constraints

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

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More bitmask dp problems