Leetcode 2029: Stone Game IX
Alice and Bob are playing a game with stones. The sequence of
n stones has values given in an array stones. Players take turns to remove a stone. The player who removes a stone, making the sum of all removed stones divisible by 3, loses. If all stones are removed, Bob wins automatically. Determine if Alice wins or Bob wins, assuming both play optimally.Problem
Approach
Steps
Complexity
Input: The input consists of an array `stones` representing the values of the stones. Alice and Bob alternate turns, starting with Alice. On each turn, one stone is removed.
Example: stones = [3, 2]
Constraints:
• 1 <= stones.length <= 10^5
• 1 <= stones[i] <= 10^4
Output: Return `true` if Alice wins and `false` if Bob wins.
Example:
Constraints:
Goal: The goal is to determine the winner of the game based on the values of the stones and the optimal moves by both players.
Steps:
• 1. Count the number of stones with values that leave remainders of 0, 1, and 2 when divided by 3.
• 2. Use the counts of stones with each remainder to decide the optimal moves for Alice and Bob.
• 3. Check if the sum of the removed stones after each turn is divisible by 3 to determine the winner.
Goal: Constraints for the number of stones and their values.
Steps:
• 1 <= stones.length <= 10^5
• 1 <= stones[i] <= 10^4
Assumptions:
• Players will always play optimally and aim to avoid the sum of removed stones being divisible by 3.
• Input: stones = [3, 2]
• Explanation: Alice removes the stone with value 2, and Bob removes the stone with value 3. The sum of the removed stones is 5, which is not divisible by 3, so Alice wins.
• Input: stones = [1, 1, 1]
• Explanation: Alice removes one stone (value 1), Bob removes another (value 1), and Alice removes the last one (value 1). The sum is 3, divisible by 3, so Alice loses and Bob wins.
• Input: stones = [4, 6, 2]
• Explanation: Alice removes the stone with value 2, Bob removes the stone with value 4, and Alice removes the last stone with value 6. The sum is 12, divisible by 3, so Alice wins.
Approach: To solve this problem, we need to simulate the game and determine who will win given the sequence of stones and the optimal play strategy.
Observations:
• The game is primarily determined by the number of stones that leave remainders of 0, 1, and 2 when divided by 3.
• The game ends when one player causes the sum of the removed stones to be divisible by 3.
• By analyzing the remainders of the stone values modulo 3, we can determine the optimal strategy for both Alice and Bob.
Steps:
• 1. Count the number of stones that leave a remainder of 0, 1, and 2 when divided by 3.
• 2. If there are no stones with a remainder of 1 or 2, Alice will lose because there is no optimal way to avoid the sum being divisible by 3.
• 3. Otherwise, calculate who will win based on the remainder counts and the optimal moves.
Empty Inputs:
• Not applicable since there will always be at least one stone.
Large Inputs:
• Ensure the solution is optimized for large inputs (up to 10^5 stones).
Special Values:
• If all stones are divisible by 3, Bob will always win.
Constraints:
• Ensure the algorithm is efficient enough to handle the maximum input size within the time limits.
bool stoneGameIX(vector<int>& stones) {
vector<int> m(3, 0);
for(int a: stones)
m[a % 3]++;
if(min(m[2], m[1]) == 0)
return max(m[1], m[2]) > 2 && m[0] % 2 >0;
return abs(m[1] - m[2]) > 2 || m[0] % 2 == 0;
}
1 : Function Definition
bool stoneGameIX(vector<int>& stones) {
This defines the 'stoneGameIX' function, which accepts a vector of stones and returns a boolean indicating whether the current player wins the game.
2 : Array Initialization
vector<int> m(3, 0);
This initializes a vector 'm' of size 3, used to store the counts of stones divided into 3 groups based on their remainder when divided by 3.
3 : Loop Start
for(int a: stones)
This loop iterates through each stone in the 'stones' vector, performing the modulo operation to categorize the stones into one of three groups.
4 : Update Counter
m[a % 3]++;
For each stone 'a', this increments the corresponding counter in the 'm' vector based on the result of 'a % 3'.
5 : Condition Check
if(min(m[2], m[1]) == 0)
This checks whether one of the groups (1 or 2 modulo 3) has zero stones, which will influence the game's outcome.
6 : Return Condition 1
return max(m[1], m[2]) > 2 && m[0] % 2 >0;
This checks if the maximum count between groups 1 and 2 is greater than 2 and if the count of group 0 is odd, deciding the winner.
7 : Return Condition 2
return abs(m[1] - m[2]) > 2 || m[0] % 2 == 0;
If the first condition is not met, this checks if the absolute difference between groups 1 and 2 is greater than 2 or if the count of group 0 is even, deciding the winner.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The algorithm runs in linear time relative to the number of stones.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant because we only need to track the counts of stones with different remainders modulo 3.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus