Given an array arr[] of size N, denoting values assigned to N stones, two players, Player1 and Player2, play a game of alternating turns. In each turn, a player can take 1, 2, or 3 stones from the first remaining stones with the sum of values of all the removed stones added to the player’s score. Considering that both players play optimally, the task is to print the winner of the game. If both players end the game with the same score, print “Tie”.
Examples:
Input: arr[] = {1, 2, 3, 7}
Output: Player2
Explanation: Player1 will always lose in an optimal scenario.Input: arr[] = {1, 2, 3, -9}
Output: Player1
Explanation: Player1 must choose all the three piles at the first move to win and leave Player2 with negative score.
If Player1 chooses only one stone his score will be 1 and the next move Player2 score becomes 5.
The next move Player1 will take the stone with value = -9 and lose.
If Player1 chooses two piles his score will be 3 and the next move Player2 score becomes 3.
The next move Player1 will take the stone with value = -9 and also lose.
Naive Approach: The simple approach is to pick the number of stones that will maximize the total sum of the stone’s values. As both players play optimally and Player1 starts the game, Player1 picks either 1 or 2 or 3 stones and the remaining stones passed to the next player. Therefore, the score of Player2 must be subtracted from score of Player1. The idea is to use recursion to solve the problem. Let the maximum score of Player1 be res which is obtained after the recursive calls.
- If the result, res > 0, Player1 wins
- If the result, res < 0, Player2 wins
- If the result, res == 0, then it is a tie.
The recursive tree looks like this, where some subproblems are repeated many times.
Follow the steps to solve the problem:
- Declare a recursive function, say maxScore(i), to calculate the maximum score of Player1 if the game starts at index i
- If the value of i ≥ n, return 0.
- Initialize a variable, say score as INT_MIN, to store the maximum score of Player1
- Picks 1 stone: score = max(score, arr[i] – maxScore(i + 1))
- Picks 2 stones i.e (i + 1 < N): score = max(score, arr[i] + arr[i + 1] – maxScore(i + 2))
- Picks 3 stones i.e (i + 2 < N): score = max(score, arr[i] + arr[i + 1] + arr[i + 2] – maxScore(i + 3))
- Return the value of the score.
- Store the value of maxScore(0) in a variable res.
- If the value of res>0, print “Player1”, if res<0, print “Player2”, otherwise print “Tie”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum score of Player1int maximumStonesUtil(int* arr, int n, int i){ // Base Case if (i >= n) return 0; // Variable to store maximum score int ans = INT_MIN; // Pick one stone ans = max(ans, arr[i] - maximumStonesUtil(arr, n, i + 1)); // Pick 2 stones if (i + 1 < n) ans = max(ans, arr[i] + arr[i + 1] - maximumStonesUtil(arr, n, i + 2)); // Pick 3 stones if (i + 2 < n) ans = max(ans, arr[i] + arr[i + 1] + arr[i + 2] - maximumStonesUtil(arr, n, i + 3)); // Return the score of the player return ans;}// Function to find the winner of the gamestring maximumStones(int* arr, int n){ // Store the result int res = maximumStonesUtil(arr, n, 0); // Player 1 wins if (res > 0) return "Player1"; // PLayer 2 wins else if (res < 0) return "Player2"; // Tie else return "Tie";}// Driver Codeint main(){ // Given Input int arr[] = { 1, 2, 3, 7 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call cout << maximumStones(arr, n); return 0;} |
Java
// Java program for the above approachclass GFG{// Function to find the maximum score of Player1static int maximumStonesUtil(int[] arr, int n, int i){ // Base Case if (i >= n) return 0; // Variable to store maximum score int ans = Integer.MIN_VALUE; // Pick one stone ans = Math.max(ans, arr[i] - maximumStonesUtil( arr, n, i + 1)); // Pick 2 stones if (i + 1 < n) ans = Math.max(ans, arr[i] + arr[i + 1] - maximumStonesUtil(arr, n, i + 2)); // Pick 3 stones if (i + 2 < n) ans = Math.max( ans, arr[i] + arr[i + 1] + arr[i + 2] - maximumStonesUtil(arr, n, i + 3)); // Return the score of the player return ans;}// Function to find the winner of the gamestatic String maximumStones(int[] arr, int n){ // Store the result int res = maximumStonesUtil(arr, n, 0); // Player 1 wins if (res > 0) return "Player1"; // PLayer 2 wins else if (res < 0) return "Player2"; // Tie else return "Tie";}// Driver codepublic static void main(String[] args){ int arr[] = { 1, 2, 3, 7 }; int n = arr.length; // Function Call System.out.println(maximumStones(arr, n));}}// This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approachimport sys# Function to find the maximum score of Player1def maximumStonesUtil(arr, n, i): # Base Case if (i >= n): return 0 # Variable to store maximum score ans = -sys.maxsize-1; # Pick one stone ans = max( ans, arr[i] - maximumStonesUtil( arr, n, i + 1)) # Pick 2 stones if (i + 1 < n): ans = max( ans, arr[i] + arr[i + 1]- maximumStonesUtil( arr, n, i + 2)) # Pick 3 stones if (i + 2 < n): ans = max( ans, arr[i] + arr[i + 1] + arr[i + 2]- maximumStonesUtil(arr, n, i + 3)); # Return the score of the player return ans# Function to find the winner of the gamedef maximumStones(arr, n): # Store the result res = maximumStonesUtil(arr, n, 0) # Player 1 wins if (res > 0): return "Player1" # PLayer 2 wins elif(res < 0): return "Player2" # Tie else: return "Tie"# Driver Codeif __name__ == '__main__': # Given Input arr = [ 1, 2, 3, 7 ] n = len(arr) # Function Call print(maximumStones(arr, n))# This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approachusing System; class GFG{// Function to find the maximum score of Player1static int maximumStonesUtil(int[] arr, int n, int i){ // Base Case if (i >= n) return 0; // Variable to store maximum score int ans = Int32.MinValue; // Pick one stone ans = Math.Max(ans, arr[i] - maximumStonesUtil( arr, n, i + 1)); // Pick 2 stones if (i + 1 < n) ans = Math.Max(ans, arr[i] + arr[i + 1] - maximumStonesUtil(arr, n, i + 2)); // Pick 3 stones if (i + 2 < n) ans = Math.Max( ans, arr[i] + arr[i + 1] + arr[i + 2] - maximumStonesUtil(arr, n, i + 3)); // Return the score of the player return ans;}// Function to find the winner of the gamestatic String maximumStones(int[] arr, int n){ // Store the result int res = maximumStonesUtil(arr, n, 0); // Player 1 wins if (res > 0) return "Player1"; // PLayer 2 wins else if (res < 0) return "Player2"; // Tie else return "Tie";} // Driver Codepublic static void Main(){ int[] arr = { 1, 2, 3, 7 }; int n = arr.Length; // Function Call Console.WriteLine(maximumStones(arr, n));}}// This code is contributed by code_hunt. |
Javascript
<script> // Javascript program for the above approach // Function to find the maximum score of Player1 function maximumStonesUtil(arr, n, i) { // Base Case if (i >= n) return 0; // Variable to store maximum score let ans = Number.MIN_VALUE; // Pick one stone ans = Math.max(ans, arr[i] - maximumStonesUtil(arr, n, i + 1)); // Pick 2 stones if (i + 1 < n) ans = Math.max(ans, arr[i] + arr[i + 1] - maximumStonesUtil(arr, n, i + 2)); // Pick 3 stones if (i + 2 < n) ans = Math.max( ans, arr[i] + arr[i + 1] + arr[i + 2] - maximumStonesUtil(arr, n, i + 3)); // Return the score of the player return ans; } // Function to find the winner of the game function maximumStones(arr, n) { // Store the result let res = maximumStonesUtil(arr, n, 0); // Player 1 wins if (res < 0) return "Player1"; // PLayer 2 wins else if (res > 0) return "Player2"; // Tie else return "Tie"; } let arr = [ 1, 2, 3, 7 ]; let n = arr.length; // Function Call document.write(maximumStones(arr, n));// This code is contributed by rameshtravel07.</script> |
Output
Player2
Time Complexity: O(3N)
Auxiliary Space: O(N)
Efficient Approach: To optimize the above approach, the idea is to use dynamic programming. The given problem has optimal substructure property and overlapping subproblems. Use memoization by creating a 1D table, dp of size N to store the results of the recursive calls.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum score of Player 1int maximumStonesUtil(int* arr, int n, int i, vector<int>& dp){ // Base Case if (i >= n) return 0; int& ans = dp[i]; // If the result is already computed, then // return the result if (ans != -1) return ans; // Variable to store maximum score ans = INT_MIN; // Pick one stone ans = max( ans, arr[i] - maximumStonesUtil(arr, n, i + 1, dp)); // Pick 2 stones if (i + 1 < n) ans = max(ans, arr[i] + arr[i + 1] - maximumStonesUtil(arr, n, i + 2, dp)); // Pick 3 stones if (i + 2 < n) ans = max(ans, arr[i] + arr[i + 1] + arr[i + 2] - maximumStonesUtil(arr, n, i + 3, dp)); // Return the score of the player return ans;}// Function to find the winner of the gamestring maximumStones(int* arr, int n){ // Create a 1D table, dp of size N vector<int> dp(n, -1); // Store the result int res = maximumStonesUtil(arr, n, 0, dp); // Player 1 wins if (res > 0) return "Player1"; // PLayer 2 wins else if (res < 0) return "Player2"; // Tie else return "Tie";}// Driver Codeint main(){ // Given Input int arr[] = { 1, 2, 3, 7 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call cout << maximumStones(arr, n); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ static int ans = 0; // Function to find the maximum score of Player 1static int maximumStonesUtil(int[] arr, int n, int i, int[] dp){ // Base Case if (i >= n) return 0; ans = dp[i]; // If the result is already computed, then // return the result if (ans != -1) return ans; // Variable to store maximum score ans = Integer.MIN_VALUE; // Pick one stone ans = Math.max( ans, arr[i] - maximumStonesUtil(arr, n, i + 1, dp)); // Pick 2 stones if (i + 1 < n) ans = Math.max(ans, arr[i] + arr[i + 1] - maximumStonesUtil(arr, n, i + 2, dp)); // Pick 3 stones if (i + 2 < n) ans = Math.max(ans, arr[i] + arr[i + 1] + arr[i + 2] - maximumStonesUtil(arr, n, i + 3, dp)); // Return the score of the player return ans;}// Function to find the winner of the gamestatic String maximumStones(int []arr, int n){ // Create a 1D table, dp of size N int []dp = new int[n]; Arrays.fill(dp, -1); // Store the result int res = maximumStonesUtil(arr, n, 0, dp); // Player 1 wins if (res > 0) return "Player1"; // PLayer 2 wins else if (res < 0) return "Player2"; // Tie else return "Tie";}// Driver Codepublic static void main(String[] args){ // Given Input int arr[] = { 1, 2, 3, 7 }; int n = arr.length; // Function Call System.out.print(maximumStones(arr, n));}}// This code is contributed by Amit Katiyar |
Python3
# Python program for the above approach# Function to find the maximum score of Player 1def maximumStonesUtil(arr, n, i, dp): # Base Case if (i >= n): return 0 ans = dp[i] # If the result is already computed, then # return the result if (ans != -1): return ans # Variable to store maximum score ans = -2**31 # Pick one stone ans = max( ans, arr[i] - maximumStonesUtil(arr, n, i + 1, dp)) # Pick 2 stones if (i + 1 < n): ans = max(ans, arr[i] + arr[i + 1] - maximumStonesUtil(arr, n, i + 2, dp)) # Pick 3 stones if (i + 2 < n): ans = max(ans, arr[i] + arr[i + 1] + arr[i + 2] - maximumStonesUtil(arr, n, i + 3, dp)) # Return the score of the player return ans# Function to find the winner of the gamedef maximumStones(arr, n): # Create a 1D table, dp of size N dp =[-1]*n # Store the result res = maximumStonesUtil(arr, n, 0, dp) # Player 1 wins if (res > 0): return "Player1" # PLayer 2 wins elif (res < 0): return "Player2" # Tie else: return "Tie"# Driver Code# Given Inputarr = [1, 2, 3, 7] n = len(arr)# Function Callprint(maximumStones(arr, n))# This code is contributed by shivani |
C#
// C# program for the above approachusing System;public class GFG{ static int ans = 0; // Function to find the maximum score of Player 1static int maximumStonesUtil(int[] arr, int n, int i, int[] dp){ // Base Case if (i >= n) return 0; ans = dp[i]; // If the result is already computed, then // return the result if (ans != -1) return ans; // Variable to store maximum score ans = int.MinValue; // Pick one stone ans = Math.Max( ans, arr[i] - maximumStonesUtil(arr, n, i + 1, dp)); // Pick 2 stones if (i + 1 < n) ans = Math.Max(ans, arr[i] + arr[i + 1] - maximumStonesUtil(arr, n, i + 2, dp)); // Pick 3 stones if (i + 2 < n) ans = Math.Max(ans, arr[i] + arr[i + 1] + arr[i + 2] - maximumStonesUtil(arr, n, i + 3, dp)); // Return the score of the player return ans;}// Function to find the winner of the gamestatic String maximumStones(int []arr, int n){ // Create a 1D table, dp of size N int []dp = new int[n]; for(int i = 0; i < n; i++) dp[i]=-1; // Store the result int res = maximumStonesUtil(arr, n, 0, dp); // Player 1 wins if (res > 0) return "Player1"; // PLayer 2 wins else if (res < 0) return "Player2"; // Tie else return "Tie";}// Driver Codepublic static void Main(String[] args){ // Given Input int []arr = { 1, 2, 3, 7 }; int n = arr.Length; // Function Call Console.Write(maximumStones(arr, n));}}// This code contributed by shikhasingrajput |
Javascript
<script>// Javascript program for the above approachlet ans = 0 ; // Function to find the maximum score of Player 1function maximumStonesUtil( arr, n, i, dp){ // Base Case if (i >= n) return 0; ans = dp[i]; // If the result is already computed, then // return the result if (ans != -1) return ans; // Variable to store maximum score ans = -Math.pow(2,31); // Pick one stone ans = Math.max( ans, arr[i] - maximumStonesUtil(arr, n, i + 1, dp)); // Pick 2 stones if (i + 1 < n) ans = Math.max(ans, arr[i] + arr[i + 1] - maximumStonesUtil(arr, n, i + 2, dp)); // Pick 3 stones if (i + 2 < n) ans = Math.max(ans, arr[i] + arr[i + 1] + arr[i + 2] - maximumStonesUtil(arr, n, i + 3, dp)); // Return the score of the player return ans;}// Function to find the winner of the gamefunction maximumStones(arr, n){ // Create a 1D table, dp of size N let dp = new Array(n).fill(-1); // Store the result let res = maximumStonesUtil(arr, n, 0, dp); // Player 1 wins if (res > 0) return "Player1"; // PLayer 2 wins else if (res < 0) return "Player2"; // Tie else return "Tie";} // Driver Code let arr= [ 1, 2, 3, 7 ]; let n = arr.length; // Function Call document.write(maximumStones(arr, n));// This code is contributed by jana_sayantan.<script> |
Output
Player2
Time Complexity: O(N)
Auxiliary Space: O(N)
Efficient Approach: Using the DP Tabulation method ( Iterative approach )
The approach to solving this problem is the same but DP tabulation(bottom-up) method is better than the Dp + memoization(top-down) because the memoization method needs extra stack space of recursion calls.
Steps to solve this problem:
- Create a DP of size n+3 to store the solution of the subproblems.
- Initialize the DP with base cases dp[n] = dp[n+1] = dp[n+2] = 0.
- Now Iterate over subproblems to get the value of the current problem from the previous computation of subproblems stored in DP
- Print the final result
- if dp[0] > 0 print player1.
- if dp[0] < 0 print player2.
- else print tie.
Implementation:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the winner of gamestring maximumStones(int* arr, int n){ // Create a 1D table, dp of size N+3 vector<int> dp(n + 3); // Initialize the table for the // last 3 stones dp[n] = dp[n + 1] = dp[n + 2] = 0; // Calculate the table for the // remaining stones in reverse order for (int i = n - 1; i >= 0; i--) { // Pick one stone int a = arr[i] - dp[i + 1]; int b = -1 , c= -1; if(i+1 == n){ b = arr[i]- dp[i + 2]; c = arr[i] - dp[i + 3]; } else if ( i+2 == n){ c = arr[i] + arr[i + 1] - dp[i + 3]; } if(b==-1) b = arr[i] + arr[i + 1] - dp[i + 2]; if(c == -1) c = arr[i] + arr[i + 1] + arr[i + 2] - dp[i + 3]; dp[i] = max(a,max(b,c)); } // Player 1 wins if (dp[0] > 0) return "Player1"; // PLayer 2 wins else if (dp[0] < 0) return "Player2"; // Tie else return "Tie";}// Driver Codeint main(){ // Given Input int arr[] = { 1, 2, 3, 7 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call cout << maximumStones(arr, n); return 0;} |
Java
import java.util.*;public class Main { // Function to find the winner of the game public static String maximumStones(int[] arr, int n) { // Create a 1D table, dp of size N+3 int[] dp = new int[n + 3]; // Initialize the table for the // last 3 stones dp[n] = dp[n + 1] = dp[n + 2] = 0; // Calculate the table for the // remaining stones in reverse order for (int i = n - 1; i >= 0; i--) { // Pick one stone int a = arr[i] - dp[i + 1]; int b = -1, c = -1; if (i + 1 == n) { b = arr[i] - dp[i + 2]; c = arr[i] - dp[i + 3]; } else if (i + 2 == n) { c = arr[i] + arr[i + 1] - dp[i + 3]; } if (b == -1) b = arr[i] + arr[i + 1] - dp[i + 2]; if (c == -1) c = arr[i] + arr[i + 1] + arr[i + 2] - dp[i + 3]; dp[i] = Math.max(a, Math.max(b, c)); } // Player 1 wins if (dp[0] > 0) return "Player1"; // PLayer 2 wins else if (dp[0] < 0) return "Player2"; // Tie else return "Tie"; } // Driver Code public static void main(String[] args) { // Given Input int[] arr = { 1, 2, 3, 7 }; int n = arr.length; // Function Call System.out.println(maximumStones(arr, n)); }} |
Python
# Function to find the winner of the gamedef maximumStones(arr, n): # Create a 1D table, dp of size N+3 dp = [0] * (n+3) # Initialize the table for the # last 3 stones dp[n] = dp[n + 1] = dp[n + 2] = 0 # Calculate the table for the # remaining stones in reverse order for i in range(n-1, -1, -1): # Pick one stone a = arr[i] - dp[i + 1] b = c = -1 if i+1 == n: b = arr[i] - dp[i + 2] c = arr[i] - dp[i + 3] elif i+2 == n: c = arr[i] + arr[i + 1] - dp[i + 3] if b == -1: b = arr[i] + arr[i + 1] - dp[i + 2] if c == -1: c = arr[i] + arr[i + 1] + arr[i + 2] - dp[i + 3] dp[i] = max(a, max(b, c)) # Player 1 wins if dp[0] > 0: return "Player1" # Player 2 wins elif dp[0] < 0: return "Player2" # Tie else: return "Tie"# Driver Codeif __name__ == '__main__': # Given Input arr = [1, 2, 3, 7] n = len(arr) # Function Call print(maximumStones(arr, n)) |
C#
using System;class GFG { // Function to find the winner of the game "Maximum Stones" // and return "Player1", "Player2", or "Tie" public static string MaximumStones(int[] arr, int n) { // Create an array to store the maximum stones each player // can collect starting from the i-th position int[] dp = new int[n + 3]; // Initialize the last three elements as // 0 (no stones available after the last position) dp[n] = dp[n + 1] = dp[n + 2] = 0; // Iterate through the array from right to left to // calculate the maximum stones each player can collect for (int i = n - 1; i >= 0; i--) { // Calculate the maximum stones Player1 can collect // starting from the i-th position int a = arr[i] - dp[i + 1]; // Initialize variables to store the maximum stones // Player2 can collect from the next two positions int b = -1, c = -1; // If there is only one position left after the i-th // position, calculate the maximum stones Player2 can collect // from that position if (i + 1 == n) { b = arr[i] - dp[i + 2]; c = arr[i] - dp[i + 3]; } // If there are two positions left after the i-th position, // calculate the maximum stones Player2 can collect from those // two positions else if (i + 2 == n) { c = arr[i] + arr[i + 1] - dp[i + 3]; } // If there are more than two positions left after the i-th position, // calculate the maximum stones Player2 can collect from the next three positions if (b == -1) b = arr[i] + arr[i + 1] - dp[i + 2]; if (c == -1) c = arr[i] + arr[i + 1] + arr[i + 2] - dp[i + 3]; // Calculate the maximum stones that Player1 can collect starting from the i-th position dp[i] = Math.Max(a, Math.Max(b, c)); } // Determine the winner based on the maximum stones Player1 // can collect from the first position if (dp[0] > 0) return "Player1"; else if (dp[0] < 0) return "Player2"; else return "Tie"; } public static void Main(string[] args) { int[] arr = { 1, 2, 3, 7 }; int n = arr.Length; Console.WriteLine(MaximumStones(arr, n)); }} |
Javascript
// Function to find the winner of the gamefunction maximumStones(arr) { let n = arr.length; // Create an array dp of size N+3 and initialize it with 0 let dp = Array(n + 3).fill(0); // Initialize the table for the last 3 stones dp[n] = dp[n + 1] = dp[n + 2] = 0; // Calculate the table for the remaining stones in reverse order for (let i = n - 1; i >= 0; i--) { // Pick one stone let a = arr[i] - dp[i + 1]; let b = c = -1; if (i + 1 === n) { b = arr[i] - dp[i + 2]; c = arr[i] - dp[i + 3]; } else if (i + 2 === n) { c = arr[i] + arr[i + 1] - dp[i + 3]; } if (b === -1) { b = arr[i] + arr[i + 1] - dp[i + 2]; } if (c === -1) { c = arr[i] + arr[i + 1] + arr[i + 2] - dp[i + 3]; } dp[i] = Math.max(a, Math.max(b, c)); } // Player 1 wins if (dp[0] > 0) { return "Player1"; } // Player 2 wins else if (dp[0] < 0) { return "Player2"; } // Tie else { return "Tie"; }}// Given Inputlet arr = [1, 2, 3, 7];// Function Callconsole.log(maximumStones(arr));// This code is contributed by srinivasteja |
Output
Player2
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
