Can I Win - Practice Coding Problems

Can I Win - Problem

Math Dynamic Programming Bit Manipulation Memoization Game Theory Bitmask Medium

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.

Input & Output

Example 1 — First Player Can Win Immediately

$ Input: maxChoosableInteger = 10, desiredTotal = 11

› Output: false

💡 Note: First player cannot guarantee a win. If player 1 picks any number from 1-10, player 2 can pick a number that reaches or exceeds 11.

Example 2 — Small Numbers, Strategic Play

$ Input: maxChoosableInteger = 10, desiredTotal = 40

› Output: true

💡 Note: First player can force a win by making strategic choices that put the second player in losing positions.

Example 3 — Immediate Win

$ Input: maxChoosableInteger = 5, desiredTotal = 5

› Output: true

💡 Note: First player wins immediately by choosing 5, which reaches the desired total.

Constraints

1 ≤ maxChoosableInteger ≤ 20
0 ≤ desiredTotal ≤ 300

Visualization

Tap to expand

Understanding the Visualization

Game Setup

Two players, numbers 1 to maxChoose, target total

Strategy

Each player tries to force opponent into losing position

Result

First player wins if any move guarantees victory

Key Takeaway

🎯 Key Insight: Use minimax with memoization - the current player wins if any move forces the opponent into a losing position

Asked in

G Google 25 M Microsoft 18 a Amazon 15

This is a game theory problem where we determine if the first player can force a win. The key insight is to use memoization with bit manipulation to represent game states efficiently. Best approach uses memoization with bitmasks. Time: O(2^n × n), Space: O(2^n)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Brute Force	O(2^n × n)	O(n)	Try all possible moves recursively without memoization
Memoization with Bit Manipulation	O(2^n × n)	O(2^n)	Use memoization with bitmask to avoid recalculating same game states

Recursive Brute Force — Algorithm Steps

Try each available number
Recursively check if opponent wins from new state
Return true if any move makes opponent lose

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Move

Pick an available number

Recurse

See if opponent can win from new state

Backtrack

Try next move if current doesn't guarantee win

Code -

solution.c — C

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

bool canWin(bool* used, int currentTotal, int maxChoosableInteger, int desiredTotal) {
    for (int i = 1; i <= maxChoosableInteger; i++) {
        if (!used[i]) {
            if (currentTotal + i >= desiredTotal) {
                return true;
            }
            used[i] = true;
            if (!canWin(used, currentTotal + i, maxChoosableInteger, desiredTotal)) {
                used[i] = false;
                return true;
            }
            used[i] = false;
        }
    }
    return false;
}

bool solution(int maxChoosableInteger, int desiredTotal) {
    // Quick win check
    if (maxChoosableInteger >= desiredTotal) {
        return true;
    }
    
    // Impossible to win check
    int totalSum = maxChoosableInteger * (maxChoosableInteger + 1) / 2;
    if (totalSum < desiredTotal) {
        return false;
    }
    
    bool* used = (bool*)calloc(maxChoosableInteger + 1, sizeof(bool));
    bool result = canWin(used, 0, maxChoosableInteger, desiredTotal);
    free(used);
    return result;
}

int main() {
    int maxChoosableInteger, desiredTotal;
    scanf("%d", &maxChoosableInteger);
    scanf("%d", &desiredTotal);
    bool result = solution(maxChoosableInteger, desiredTotal);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n × n)

Each number can be used or not (2^n states) and we try n choices at each state

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth up to n levels

⚡ Linearithmic Space

98.6K Views

Medium Frequency

~35 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler