Find if Digit Game Can Be Won

Difficulty: Easy | Acceptance: 81.60% | Paid: No Topics: Array, Math

You are given a 0-indexed integer array nums. Alice and Bob are playing a game. In each turn, a player picks a digit from the array and removes it.

Alice starts the game. In her turn, she must pick a digit from an even index. If the picked digit is even, she wins the game.

In Bob’s turn, he must pick a digit from an odd index. If the picked digit is odd, he wins the game.

The game ends when a player cannot pick a digit that satisfies the condition.

Return true if Alice will win the game, otherwise return false.

• Examples
• Constraints
• Optimal Single Pass
• Brute Force Simulation

Examples

Example 1

Input:

nums = [1,2,3,4,10]

Output:

false

Explanation: Alice cannot win by choosing either single-digit or double-digit numbers.

Example 2

Input:

nums = [1,2,3,4,5,14]

Output:

true

Explanation: Alice can win by choosing single-digit numbers which have a sum equal to 15.

Example 3

Input:

nums = [5,5,5,25]

Output:

true

Explanation: Alice can win by choosing double-digit numbers which have a sum equal to 25.

Constraints

1 <= nums.length <= 100
0 <= nums[i] <= 9

Optimal Single Pass

Intuition The game can be simulated by iterating through the array with a specific index pattern. Alice checks indices 0, 1, 3, 5…, while Bob checks indices 2, 4, 6… based on how elements shift after removals. We can use a pointer to jump between these indices without modifying the array.

Steps

• Initialize a pointer i = 0 and a turn flag (0 for Alice, 1 for Bob).
• Loop while i is within bounds.
• If it’s Alice’s turn:
  • Check if nums[i] is even. If yes, return true.
  • Move pointer i += 2 (skip the next element Bob will check).
• If it’s Bob’s turn:
  • Check if nums[i] is odd. If yes, return false.
  • Move pointer i -= 1 (move back to the element Alice needs to check next).
• Toggle turn.
• If the loop completes, Alice wins because Bob ran out of moves.

class Solution:
    def canAliceWin(self, nums: list[int]) -> bool:
        n = len(nums)
        i = 0
        turn = 0  # 0 for Alice, 1 for Bob
        while i < n:
            if turn == 0:
                if nums[i] % 2 == 0:
                    return True
                i += 2
            else:
                if nums[i] % 2 == 1:
                    return False
                i -= 1
            turn ^= 1
        return True

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Most efficient solution, avoids extra memory allocation.

Brute Force Simulation

Intuition Simulate the game exactly as described by physically removing elements from a list structure. This approach directly models the game state changes.

Steps

• Create a mutable copy of the array (e.g., a list or deque).
• Loop while the list is not empty.
• Alice’s turn: Check the first element (index 0). If even, return true. Otherwise, remove it.
• If the list becomes empty after Alice’s move, Bob cannot move, so return true.
• Bob’s turn: Check the second element (index 1). If odd, return false. Otherwise, remove it.
• If the list becomes empty after Bob’s move, Alice cannot move, so return false.

class Solution:
    def canAliceWin(self, nums: list[int]) -> bool:
        arr = nums[:]
        while arr:
            # Alice's turn
            if arr[0] % 2 == 0:
                return True
            arr.pop(0)
            if not arr:
                return True # Bob cannot move
            # Bob's turn
            if arr[1] % 2 == 1:
                return False
            arr.pop(1)
        return False

Complexity

• Time: O(n²)
• Space: O(n)
• Notes: Removing elements from the front of an array/list is O(n), leading to quadratic time complexity. Less efficient but conceptually simple.