Last updated on January 12th, 2025 at 03:46 am

Here, we see a Can I Win LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Graph, Tree, Union-Find

Companies

Google

Level of Question

Medium

Can I Win LeetCode Solution

1. Problem Statement

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.

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

2. Coding Pattern Used in Solution

The coding pattern used in this problem is “Bitmasking with Memoization”. The problem involves using bitmasking to represent the state of the game (which numbers have been chosen) and memoization to store previously computed results for optimization.

3. Code Implementation in Different Languages

1. Can I Win C++

class Solution {
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        int sum = maxChoosableInteger*(maxChoosableInteger+1)/2;
        if (desiredTotal < 2) return true;
        else if (sum < desiredTotal) return false;
        else if (sum == desiredTotal) return maxChoosableInteger%2;
        else return dfs(maxChoosableInteger, desiredTotal, 0);
    }
    bool dfs(int maxChoosableInteger, int desiredTotal, int k){
        if (mem[k] != 0) return mem[k] > 0;
        if (desiredTotal <= 0) return false;
        for (int i = 0; i < maxChoosableInteger; ++i)
        if (!(k&(1<<i)) && !dfs(maxChoosableInteger, desiredTotal-i-1, k|(1<<i))) {
            mem[k] = 1;
            return true;
        }
        mem[k] = -1;
        return false;
    }
    int mem[1<<20] = {};
};

2. Can I Win Java

class Solution {
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        int totalPossibleSum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
        if (totalPossibleSum < desiredTotal) return false;
        Map<Integer, Boolean> memo = new HashMap<>();
        return dp(desiredTotal, 0, maxChoosableInteger, memo);
    }
    private boolean dp(int goal, int state, int maxChoosable, Map<Integer, Boolean> memo) {
        if (memo.containsKey(state)) {
            return memo.get(state);
        }
        boolean result = false;
        for (int i = 1; i <= maxChoosable; i++) {
            boolean isAvailable = (state >> i) % 2 == 0;
            if (!isAvailable) {
                continue;
            }
            if (goal - i <= 0) {
                result = true;
                break;
            }
            int currMask = 1 << i;
            int newState = state | currMask;
            boolean rivalResult = dp(goal - i, newState, maxChoosable, memo);
            if (!rivalResult) {
                result = true;
                break;
            }
        }
        memo.put(state, result);
        return result;
    }
}

3. Can I Win JavaScript

var canIWin = function (maxChoosableInteger, desiredTotal) {
  if (maxChoosableInteger >= desiredTotal) return true;
  if ((maxChoosableInteger + 1) * maxChoosableInteger / 2 < desiredTotal) return false;
  const memo = new Map;
  const canWin = (state, total) => {
    if (total >= desiredTotal) return false;
    if (memo.has(state)) return memo.get(state);
    for (let i = 1; i <= maxChoosableInteger; i++) {
      const mask = 1 << i;
      if ((state & mask) === 0) {
        const next = state | mask;
        if (!canWin(next, total + i)) {
          memo.set(state, true);
          return true;
        }
      }
    }
    memo.set(state, false);
    return false;
  }
  return canWin(0, 0)
};

3.4 Can I Win Python

class Solution(object):
    def canIWin(self, maxChoosableInteger, desiredTotal):
        has_used = lambda flag, x: flag & (1<<x)
        is_odd = lambda x: x % 2 == 1
        def can_player_win_on(target, bitflag):
            if target <= 0:
                return False
            for call_number in range(1, maxChoosableInteger+1):
                if has_used( bitflag, call_number ):
                    continue
                if not can_player_win_on(target - call_number, bitflag | (1<<call_number) ):
                    return True
            return False
        S = maxChoosableInteger * (maxChoosableInteger+1) // 2
        if S < desiredTotal:
            return False
        elif desiredTotal <= 0:
            return True
        elif S == desiredTotal and is_odd(maxChoosableInteger):
            return True
        return can_player_win_on(desiredTotal, bitflag=0 )

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(2ⁿ * n)	O(2ⁿ)
Java	O(2ⁿ * n)	O(2ⁿ)
JavaScript	O(2ⁿ * n)	O(2ⁿ)
Python	O(2ⁿ * n)	O(2ⁿ)

The problem uses bitmasking to efficiently represent the state of the game.
Memoization is used to optimize the recursive solution by avoiding redundant calculations.
The time complexity is exponential due to the large number of possible states 2ⁿ, but memoization significantly reduces redundant computations.