Stone Game

Approach 1: Dynamic Programming

This Problem is an example of a minimax algorithm. The key of the minimax algorithm is that A will always choose the maximum among all his choices (the same as B), and then B will always leave the minimum of the rest choices to A when it switches back to A (the same as A leaves to B).

Algorithm

1. Initialize a 2D-DP array of size (N+2) x (N+2) where N is the number of piles and set all values as 0.
2. Suppose we currently have piles[i], piles[i+1],.....piles[j].
3. In order to maximize its stones, Player A selects either piles[i] or piles[j].
4. In order to minimize stones of A, Player B selects either piles[i] or piles[j].
5. If A has more stones than B, return true.

Code

• C++

C++

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

bool stoneGame(vector<int>& piles) {
    int n = piles.size();
    vector<vector<int>> dp(n+2,vector<int> (n+2,0));
    for(int size = 1; size <= n; ++size)
        for(int i = 0, j = size - 1; j < n; ++i, ++j){
            int turn = (j + i + n) % 2; 
            if(turn == 1)
                dp[i+1][j+1] = max(piles[i] + dp[i+2][j+1], piles[j] + dp[i+1][j]);
            else
                dp[i+1][j+1] = min(-piles[i] + dp[i+2][j+1], -piles[j] + dp[i+1][j]);
        }
    return dp[1][n] > 0;
}
    
int main()
{
    vector<int> piles={5,3,4,5};
    bool ans=stoneGame(piles);
    if(ans){
        cout<<"True\n";
    }
    else{
        cout<<"False\n";
    }

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Complexity Analysis

Time Complexity: O(N²)

Space Complexity: O(N²)

Approach 2: Mathematics

Interesting observation about the Stone Game Problem. Because Player A is the first to choose a stone pile and the number of piles is even, an interesting fact emerges: Since Player A starts first, he/she has the choice to always choose the odd indexed piles or always choose even indexed piles.

Case 1: A chooses even piles.

If Player A wants to pick piles in even positions and chooses the first pile, which is pile at index 0, then Player B can pick piles[1] or piles[n-1].

Player A can always choose piles in even places during his turn, while Player B can only choose piles in odd positions.

Case 2: A chooses odd piles.

If Player A wants to pick piles in odd positions and chooses the last pile, which is pile at index n-1, then Player B can pick piles[0] or piles[n-2].

Player A can always choose piles in odd places during his turn, while Player B can only choose piles in even positions.

As we all know, the total number of stones in the piles is odd.

Player A just picks all evens and wins if the amount of piles[even] is greater than the sum of piles[odd].

Player B just picks all odds and wins if the amount of piles[even] is less than the sum of piles[odd].

So regardless of the case, There always exists a winning move for Player A.

Code:

• C++

C++

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

bool stoneGame(vector<int>& piles) {
    return true;
}
    
int main()
{
    vector<int> piles={5,3,4,5};
    bool ans=stoneGame(piles);
    if(ans){
        cout<<"True\n";
    }
    else{
        cout<<"False\n";
    }

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Complexity Analysis

Time Complexity: O(1)

Space Complexity: O(1)

Check out Longest Common Substring

Frequently Asked Questions

What is minimax in game theory?

In the Minimax Algorithm, the two players are called maximizer and minimizer, respectively. The maximizer tries to maximize the score and get the highest score possible, while the minimizer attempts to do the opposite and get the lowest score possible.

What is the most efficient solution to the problem Stone Game?

The Stone Game problem can be solved in O(1) space and time complexity because there always exists a winning move for the first player. So we can always return true.

What is the game of stones?

In the stone game, two players, A and B, take turns removing piles of stones from either end of a row with N piles (all containing an odd number of stones). Player A starts. The goal is for Player A to end up with more stones than Player B. Return true if Player A can win, otherwise, return false.

Conclusion

Stone Game question is asked in numerous interviews based on dynamic programming and game theory. Learn more about dynamic programming.

Although it's always suggested to solve the problem using a naive approach but observing the solution and problem carefully can yield great results. Observation is a great tool in developing the most efficient solutions and can improve our problem-solving skills.

Check out this problem - Optimal Strategy For A Game

Check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc., on Coding Ninjas Studio.