Can I Win

Medium
1615.

Can I Win

Can I Win is a medium coding problem on dynamic programming, math and bit manipulation, asked in Amazon, Google and LinkedIn interviews.

Two players share a running total that starts at 0. They take turns, and on each turn a player picks one of the integers 1, 2, …, maxChoosableInteger and adds it to the total. Each integer can be picked only once in the whole game, by either player.

The player whose pick makes the running total reach or exceed desiredTotal wins.

The first player moves first. Assuming both players always play optimally, return true if the first player can force a win, and false otherwise. (If the numbers run out before the total is reached, nobody reaches it, and the first player has not won.)

Example 1

Input
maxChoosableInteger = 10, desiredTotal = 11
Output
false
Explanation
Whatever x the first player picks, the second player picks 11 - x (always available and different from x) and reaches 11.

Example 2

Input
maxChoosableInteger = 10, desiredTotal = 0
Output
true
Explanation
The target is already met before anyone moves.

Example 3

Input
maxChoosableInteger = 10, desiredTotal = 1
Output
true
Explanation
Any pick reaches 1.

Constraints

  • 1 <= maxChoosableInteger <= 20
  • 0 <= desiredTotal <= 300
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} maxChoosableInteger
 * @param {number} desiredTotal
 * @return {boolean}
 */
var canIWin = function(maxChoosableInteger, desiredTotal) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Can I Win — Solution in Python, Java & C++

Can I Win solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon and Google.

Can I Win is a medium coding problem on dynamic programming, math and bit manipulation, asked in Amazon, Google and LinkedIn interviews.

Problem statement

Two players share a running total that starts at 0. They take turns, and on each turn a player picks one of the integers 1, 2, …, maxChoosableInteger and adds it to the total. Each integer can be picked only once in the whole game, by either player.

The player whose pick makes the running total reach or exceed desiredTotal wins.

The first player moves first. Assuming both players always play optimally, return true if the first player can force a win, and false otherwise. (If the numbers run out before the total is reached, nobody reaches it, and the first player has not won.)

Example 1

Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false
Explanation: Whatever x the first player picks, the second player picks 11 - x (always available and different from x) and reaches 11.

Example 2

Input: maxChoosableInteger = 10, desiredTotal = 0
Output: true
Explanation: The target is already met before anyone moves.

Example 3

Input: maxChoosableInteger = 10, desiredTotal = 1
Output: true
Explanation: Any pick reaches 1.

Constraints

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

Hints for Can I Win

  1. Hint 1

    Two quick answers first: a target <= 0 is already won, and if 1 + 2 + … + maxChoosableInteger < desiredTotal nobody can ever reach it.

  2. Hint 2

    The remaining total is determined by which numbers have been used, so the whole game state is the set of used numbers — at most 2^20 states. Encode it as a bitmask.

  3. Hint 3

    The player to move wins from a state if some unused i either reaches the target immediately (i >= remaining) or leads to a state from which the opponent loses. Memoise win/lose per mask.

How to solve Can I Win

This is a finite two-player game without chance, so every position is a forced win or a forced loss for the player to move. The position is fully described by the set of numbers already used (the remaining target follows from it), so memoising over a bitmask of used numbers makes the game tree a DAG of at most 2^m nodes.

Approach

  1. If desiredTotal <= 0 return true; if m(m+1)/2 < desiredTotal return false (m = maxChoosableInteger).
  2. Define win(used, remaining): for each i in 1..m not in used, if i >= remaining or !win(used | bit(i), remaining - i), return true. Otherwise return false.
  3. Cache the result by used (an array of size 2^(m+1) with unknown / win / lose).
  4. Return win(0, desiredTotal).

Why it works

A move that reaches the target wins on the spot; any other move hands the opponent the position used | bit(i) with them to move. The mover can force a win exactly when some move leaves the opponent in a losing position — the standard win/lose recursion. Since remaining = desiredTotal - sum(used), two calls with the same mask always have the same remaining total, so caching by mask alone is sound.

Complexity

  • Time — O(2^m * m)
  • Space — O(2^m)

Pitfalls

  • Without the sum < desiredTotal check, a game where nobody can win would be reported as a loss for the first player only by accident of the recursion — the check makes it explicit and fast.
  • desiredTotal = 0 is a win for the first player even though no move is made.
  • Memoising on (used, remaining) as a string key is correct but slow; the mask alone is enough.

Reference solution

Python

def canIWin(maxChoosableInteger: int, desiredTotal: int) -> bool:
    m = maxChoosableInteger
    if desiredTotal <= 0:
        return True
    if m * (m + 1) // 2 < desiredTotal:
        return False
    memo = {}

    def win(used, remaining):
        if used in memo:
            return memo[used]
        res = False
        for i in range(1, m + 1):
            bit = 1 << i
            if used & bit:
                continue
            if i >= remaining or not win(used | bit, remaining - i):
                res = True
                break
        memo[used] = res
        return res

    return win(0, desiredTotal)

Java

static byte[] canWinMemo;
static int canWinMax;

static boolean canWin(int used, int remaining) {
    if (canWinMemo[used] != 0) return canWinMemo[used] == 1;
    boolean res = false;
    for (int i = 1; i <= canWinMax; i++) {
        int bit = 1 << i;
        if ((used & bit) != 0) continue;
        if (i >= remaining || !canWin(used | bit, remaining - i)) { res = true; break; }
    }
    canWinMemo[used] = (byte) (res ? 1 : 2);
    return res;
}

public static boolean canIWin(int maxChoosableInteger, int desiredTotal) {
    int m = maxChoosableInteger;
    if (desiredTotal <= 0) return true;
    if (m * (m + 1) / 2 < desiredTotal) return false;
    canWinMax = m;
    canWinMemo = new byte[1 << (m + 1)];
    return canWin(0, desiredTotal);
}

C++

bool canWinFrom(int used, int remaining, int m, vector<signed char>& memo) {
    if (memo[used] != 0) return memo[used] == 1;
    bool res = false;
    for (int i = 1; i <= m; i++) {
        int bit = 1 << i;
        if (used & bit) continue;
        if (i >= remaining || !canWinFrom(used | bit, remaining - i, m, memo)) { res = true; break; }
    }
    memo[used] = res ? 1 : 2;
    return res;
}

bool canIWin(int maxChoosableInteger, int desiredTotal) {
    int m = maxChoosableInteger;
    if (desiredTotal <= 0) return true;
    if (m * (m + 1) / 2 < desiredTotal) return false;
    vector<signed char> memo(1 << (m + 1), 0);
    return canWinFrom(0, desiredTotal, m, memo);
}

JavaScript

var canIWin = function(maxChoosableInteger, desiredTotal) {
    var m = maxChoosableInteger;
    if (desiredTotal <= 0) return true;
    if (m * (m + 1) / 2 < desiredTotal) return false;
    var memo = new Int8Array(1 << (m + 1)); // 0 unknown, 1 win, 2 lose
    var win = function(used, remaining) {
        if (memo[used] !== 0) return memo[used] === 1;
        var res = false;
        for (var i = 1; i <= m; i++) {
            var bit = 1 << i;
            if (used & bit) continue;
            if (i >= remaining || !win(used | bit, remaining - i)) { res = true; break; }
        }
        memo[used] = res ? 1 : 2;
        return res;
    };
    return win(0, desiredTotal);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Bit Manipulation