Table of Contents

## What is Stone Game problem?

Stone Game LeetCode – Two players A and B are playing a stone game. There are even numbers of piles each pile containing some stones and the total stones in all the piles is odd. A and B are supposed to pick a pile either from the starting or end of the row one by one until no more piles are left. Player A will always start the game by picking a pile first. The player with more stones at the end wins the game. Print true if and only if player A wins the game else print false. This question is very common in LeetCode.

Therefore, the output will be true because A is the winner assuming he starts the game. Below is an example of a stone game leetcode.

### Example

**Input : **piles = {5, 3, 4, 5}

**Output : **True

**Input : **piles = {5, 3, 4, 5, 3, 7}

**Output : **True

## Dynamic Programming Method

LeetCode’s Stone Game problem can be solved using Dynamic Programming

### Algorithm

- Initialize a list containing piles of stones.
- Create a 2D-DP array and set all values as 0.
- Each player has two choices when remaining piles are piles[i], piles[i+1], …. piles[j] therefore chance of player can be found comparing j-i to n modulo 2.
- Player A either chooses piles[i] or piles[j] in order to maximize its stones.
- Player B either chooses piles[i] or piles[j] in order to minimize its stones.
- Return true if A has more stones

**Time Complexity: **O(n^{2})

**Space Complexity: **O(n^{2})

### C++ Program

#include<bits/stdc++.h> using namespace std; class Stone{ public: bool stoneGame(vector<int>& piles) { int n = piles.size(); int dp[n+2][n+2]; memset(dp, 0, sizeof(dp)); for(int size = 1; size <= n; ++size) for(int i = 0, j = size - 1; j < n; ++i, ++j){ int parity = (j + i + n) % 2; if(parity == 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(){ Stone s; vector<int> piles = {5, 3, 4, 5}; if(s.stoneGame(piles)){ cout<<"True"; } else{ cout<<"False"; } }

True

### Java Program

import java.util.*; class Stone{ static boolean stoneGame(int[] piles){ int n = piles.length; int[][] dp = new int[n+2][n+2]; for(int size = 1; size <= n; ++size) for(int i = 0; i + size <= n; ++i){ int j = i + size - 1; int parity = (j + i + n) % 2; if(parity == 1) dp[i+1][j+1] = Math.max(piles[i] + dp[i+2][j+1], piles[j] + dp[i+1][j]); else dp[i+1][j+1] = Math.min(-piles[i] + dp[i+2][j+1], -piles[j] + dp[i+1][j]); } return dp[1][n] > 0; } public static void main (String[] args){ int piles[] = {5, 3, 4, 5}; if(stoneGame(piles)){ System.out.println("True"); } else{ System.out.println("False"); } } }

Output : True

## Mathematical Or Observed Method

Interesting facts about Stone Game LeetCode. As Player A is first to choose the stone pile and number of piles is even, this lead to an interesting fact:

Player A can always choose odd piles or always choose even piles.

Let’s say :

If Player A wants to pick piles at even positions and picks the first pile that is pile at index 0, then player B can choose either piles[1] or piles[n-1].

Every turn, Player A can always choose piles at even positions and Player B can only choose piles at odd positions.

As we know that sum of stones in piles is odd.

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

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

So, Player A is always the winner in this game.

### Algorithm

- Initialize a list containing piles of stones.
- Return True.

**Time Complexity: **O(1)

**Space Complexity: **O(1)

### C++ Program

#include<bits/stdc++.h> using namespace std; class Stone{ public: bool stoneGame(vector<int>& piles) { return true; } }; int main(){ Stone s; vector<int> piles = {5, 3, 4, 5}; if(s.stoneGame(piles)){ cout<<"True"; } else{ cout<<"False"; } }

True

### Java Program

import java.util.*; class Stone{ static boolean stoneGame(int[] piles){ return true; } public static void main (String[] args){ int piles[] = {5, 3, 4, 5}; if(stoneGame(piles)){ System.out.println("True"); } else{ System.out.println("False"); } } }

True

This is the famous solution of the stone game leetcode. Stone Game LeetCode question is being asked in various interviews which are based on dynamic programming.