Last updated on October 5th, 2024 at 04:21 pm

Here, We see Can I Win LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Can I Win LeetCode Solution

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

1. Can I Win LeetCode Solution 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 LeetCode Solution 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 LeetCode Solution 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)
};

4. Can I Win LeetCode Solution 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 )