Given a numeric string str, the task is to determine the winner of the game when two players play a game optimally with the string as per the given conditions:
- Player 1 always starts first.
- In one turn, one player can remove the contiguous elements from the string and the number of elements removed will add up to his score. Player 1 will remove odd contiguous elements and Player 1 will remove even contiguous elements.
- Any player who is not able to make a move loses the game.
- After all the strings are removed, the player with the maximum score wins the game and if the scores are equal, then print “-1”.
Examples:
Input: str = “7788”
Output: -1
Explanation:
The first move for player 1 is to remove 77 and for player 2 it is 88. The score for both is 2. Hence -1.Input: str = “8822”
Output: Player 2
Explanation:
There are no odd elements, so player 1 can’t make a move, so player 2 wins.
Approach: Follow the steps below in order to solve the problem:
- Create an array A[] of size 10 to store the frequency of all the digits in the given string.
- Iterate the given string and update the frequency of each digit in the above array.
- Traverse the array A[] and take two variables as sum1 = 0 and sum2 = 0 to store the sum of scores.
- Increment sum1 if the index is odd i.e., Player 1 turn, else increment sum2 if the index is even i.e., Player 2 turn.
- After the above steps, check if sum1 is equal to sum2 then print -1 otherwise print the number of players who win the game on the basis of the score.
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 winner of the// game when both players play optimallyvoid determineWinner(string str){ // Stores the frequency of all digit vector<int> A(10); // Stores the scores of player1 // and player2 respectively int sum1 = 0, sum2 = 0; // Iterate to store frequencies for (int i = 0; i < str.length(); i++) { A[int(str[i]) - 48]++; } for (int i = 0; i <= 9; i++) { // Turn for the player1 if (i % 2 != 0) { // Add score of player1 sum1 = sum1 + A[i]; } else { // Add score of player2 sum2 = sum2 + A[i]; } } // Check if its a draw if (sum1 == sum2) { cout << "-1"; } // If score of player 1 is greater else if (sum1 > sum2) { cout << "Player 1"; } // Otherwise else { cout << "Player 2"; }}// Driver Codeint main(){ string str = "78787"; determineWinner(str); return 0;} |
Java
// Java program for the above approach import java.util.*;class GFG{// Function to find the winner of the// game when both players play optimallystatic void determineWinner(String str){ // Stores the frequency of all digit int[] A = new int[10]; // Stores the scores of player1 // and player2 respectively int sum1 = 0, sum2 = 0; // Iterate to store frequencies for(int i = 0; i < str.length(); i++) { A[(int)str.charAt(i) - 48]++; } for(int i = 0; i <= 9; i++) { // Turn for the player1 if (i % 2 != 0) { // Add score of player1 sum1 = sum1 + A[i]; } else { // Add score of player2 sum2 = sum2 + A[i]; } } // Check if its a draw if (sum1 == sum2) { System.out.print("-1"); } // If score of player 1 is greater else if (sum1 > sum2) { System.out.print("Player 1"); } // Otherwise else { System.out.print("Player 2"); }}// Driver codepublic static void main (String[] args){ String str = "78787"; determineWinner(str);}}// This code is contributed by offbeat |
Python3
# Python3 program for the above approach # Function to find the winner of the# game when both players play optimallydef determineWinner(str): # Stores the frequency of all digit A = [0 for i in range(9)]; # Stores the scores of player1 # and player2 respectively sum1 = 0; sum2 = 0; # Iterate to store frequencies for i in range(0, len(str)): A[int(str[i])] += 1; for i in range(0, 9): # Turn for the player1 if (i % 2 != 0): # Add score of player1 sum1 = sum1 + A[i]; else: # Add score of player2 sum2 = sum2 + A[i]; # Check if its a draw if (sum1 == sum2): print("-1"); # If score of player 1 is greater elif(sum1 > sum2): print("Player 1"); # Otherwise else: print("Player 2"); # Driver codeif __name__ == '__main__': str = "78787"; determineWinner(str); # This code is contributed by Amit Katiyar |
C#
// C# program for the above approach using System;class GFG{// Function to find the winner of the// game when both players play optimallystatic void determineWinner(String str){ // Stores the frequency of all digit int[] A = new int[10]; // Stores the scores of player1 // and player2 respectively int sum1 = 0, sum2 = 0; // Iterate to store frequencies for(int i = 0; i < str.Length; i++) { A[(int)str[i] - 48]++; } for(int i = 0; i <= 9; i++) { // Turn for the player1 if (i % 2 != 0) { // Add score of player1 sum1 = sum1 + A[i]; } else { // Add score of player2 sum2 = sum2 + A[i]; } } // Check if its a draw if (sum1 == sum2) { Console.Write("-1"); } // If score of player 1 is greater else if (sum1 > sum2) { Console.Write("Player 1"); } // Otherwise else { Console.Write("Player 2"); }}// Driver codepublic static void Main(String[] args){ String str = "78787"; determineWinner(str);}}// This code is contributed by Rohit_ranjan |
Javascript
<script>// Javascript program to implement// the above approach// Function to find the winner of the// game when both players play optimallyfunction determineWinner(str){ // Stores the frequency of all digit let A = Array.from({length: 10}, (_, i) => 0); // Stores the scores of player1 // and player2 respectively let sum1 = 0, sum2 = 0; // Iterate to store frequencies for(let i = 0; i < str.length; i++) { A[str[i].charCodeAt() - 48]++; } for(let i = 0; i <= 9; i++) { // Turn for the player1 if (i % 2 != 0) { // Add score of player1 sum1 = sum1 + A[i]; } else { // Add score of player2 sum2 = sum2 + A[i]; } } // Check if its a draw if (sum1 == sum2) { document.write("-1"); } // If score of player 1 is greater else if (sum1 > sum2) { document.write("Player 1"); } // Otherwise else { document.write("Player 2"); }}// Driver code let str = "78787"; determineWinner(str);</script> |
Output:
Player 1
Time Complexity: O(N)
Auxiliary Space: O(1) since it is using constant space
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!
… [Trackback]
[…] Info to that Topic: geeksforgeeks.org/determine-the-winner-of-a-game-of-deleting-characters-from-a-string/ […]