{x}
blog image

Stone Game IX

Alice and Bob continue their games with stones. There is a row of n stones, and each stone has an associated value. You are given an integer array stones, where stones[i] is the value of the ith stone.

Alice and Bob take turns, with Alice starting first. On each turn, the player may remove any stone from stones. The player who removes a stone loses if the sum of the values of all removed stones is divisible by 3. Bob will win automatically if there are no remaining stones (even if it is Alice's turn).

Assuming both players play optimally, return true if Alice wins and false if Bob wins.

 

Example 1:

Input: stones = [2,1]
Output: true
Explanation: The game will be played as follows:
- Turn 1: Alice can remove either stone.
- Turn 2: Bob removes the remaining stone. 
The sum of the removed stones is 1 + 2 = 3 and is divisible by 3. Therefore, Bob loses and Alice wins the game.

Example 2:

Input: stones = [2]
Output: false
Explanation: Alice will remove the only stone, and the sum of the values on the removed stones is 2. 
Since all the stones are removed and the sum of values is not divisible by 3, Bob wins the game.

Example 3:

Input: stones = [5,1,2,4,3]
Output: false
Explanation: Bob will always win. One possible way for Bob to win is shown below:
- Turn 1: Alice can remove the second stone with value 1. Sum of removed stones = 1.
- Turn 2: Bob removes the fifth stone with value 3. Sum of removed stones = 1 + 3 = 4.
- Turn 3: Alices removes the fourth stone with value 4. Sum of removed stones = 1 + 3 + 4 = 8.
- Turn 4: Bob removes the third stone with value 2. Sum of removed stones = 1 + 3 + 4 + 2 = 10.
- Turn 5: Alice removes the first stone with value 5. Sum of removed stones = 1 + 3 + 4 + 2 + 5 = 15.
Alice loses the game because the sum of the removed stones (15) is divisible by 3. Bob wins the game.

 

Constraints:

  • 1 <= stones.length <= 105
  • 1 <= stones[i] <= 104

Solution Explanation: Stone Game IX

This problem involves a game where two players, Alice and Bob, take turns removing stones. The player who removes a stone resulting in the sum of removed stones being divisible by 3 loses. The solution utilizes a greedy approach combined with case analysis or simulation to determine the winner.

Approach 1: Greedy + Case Discussion

This approach is more efficient. It leverages the fact that only the remainder when the stone value is divided by 3 matters.

  1. Counting Remainders: The code first counts the number of stones with remainders 0, 1, and 2 when divided by 3. This is stored in the cnt array.

  2. Case Analysis: The core logic lies in the check function. It simulates the game's progression based on the initial move.

    • If Alice starts by removing a stone with remainder 1: Bob can only remove stones with remainder 1 or 2. The game proceeds until one player has no valid moves left. The function analyzes if Alice can force a win based on this sequence of moves.

    • If Alice starts by removing a stone with remainder 2: A similar analysis is performed for this scenario.

    • The check function returns true if Alice can win given the starting scenario, otherwise it returns false.

  3. Determining Winner: The main part of the code calls check twice, once assuming Alice starts with a remainder 1 and once assuming she starts with a remainder 2. If either returns true, Alice wins; otherwise, Bob wins.

Time Complexity: O(1) because the number of iterations in check is limited by the maximum number of stones, which is not dependent on input size directly. The counting of remainders is O(n), where n is the number of stones. However, this is dominated by the constant time complexity.

Space Complexity: O(1) because we use a fixed-size array (cnt) regardless of input size.

Approach 2: Simulation

This approach simulates the game directly, but it is less efficient than approach 1.

  1. Counting Remainders: Similar to approach 1, it counts the number of stones with remainders 0, 1, and 2.

  2. Simulation: The check function simulates the game by iteratively removing stones, alternating between players. It keeps track of the current remainder and determines the winner based on whether the current player can make a move such that the total sum would not be divisible by 3.

  3. Determining Winner: The main part of the code calls check twice to simulate the game with Alice starting with a remainder 1 and then with a remainder 2.

Time Complexity: The time complexity of this approach is closer to O(n) in the worst case, as the simulation could potentially go through all the stones.

Space Complexity: O(1), similar to approach 1.

Which Approach is Better?

Approach 1 (Greedy + Case Discussion) is significantly more efficient due to its constant time complexity. Approach 2 (Simulation) is less efficient, although both produce correct answers. For large inputs, Approach 1 would be vastly superior in performance.