Given a Binary String S. 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.
- Two players take turns choosing a whole block of consecutive equal characters and deleting them from a given binary String S.
- Player 1 can choose only an odd number of consecutive equal characters and Player 2 can choose only an even number of consecutive equal characters. The player may choose nothing and count it as their turn only if it is impossible to choose anything.
- After all the characters are removed, the player with maximum scores wins the game and if scores are equal then print “-1”
Input: S = “1110011001010”
Output: Player 1
Explanation:
The selected characters will be in bold and Player 1’s score is Score_1 and Player 2’s score is Score_2 :
Turn 1 : (Player 1) “1110011001010” → “0011001010” Score_1 = 3
Turn 2 : (Player 2) “0011001010” → “00001010” Score_2 = 2
Turn 3 : (Player 1) “00001010”→ “0000010” Score_1 = 4
Turn 4: (Player 2) “0000010”
He cannot do anything as only one ‘1’ is present which is an odd number.
Also, he can’t choose the ‘0’s as they are odd (5 and 1), Therefore, Score_2 =2
Turn 5:(Player 1) “0000010”→ “000000” Score_1=5
Turn 6:(Player 2) “000000” → “” Score_2 = 2 (No ‘1’ was deleted in this turn)Final scores: Score_1 = 5 and Score_2 = 2
Therefore, Player 1 wins.Input : S = “11111101”
Output: Player 2
Explanation:
Turn 1 : (Player 1) “11111101” → “1111110” Score_1 = 3
Turn 2 : (Player 2) “1111110” → “0” Score_2 = 6
Turn 3 : (Player 1) “0” → “” Score_1 = 3Final scores: Score_1 = 3 and Score_2 = 6
Therefore, Player 2 wins.
Approach:
- If we observe this game carefully, we understand that the only consecutive 1s are contributing to the scores of these players.
- Create a list to store the lengths of the consecutive 1s in the string.
- Sort the list in descending order.
- Now iterate over the list and if the list element is odd it will be added to the score of the Player 1 and if it is even it will be added to the score of the Player 2.
- Now if the score of the Player 1 is greater than the score of the Player 2 then print “Player 1” and if the score of the Player 2 is greater than the score of the Player 1 then print “Player 2”.
- Print “-1” if there is a tie i.e., scores are the same.
Below is the implementation of the above approach.
C++
// C++ program for the above approach #include<bits/stdc++.h>using namespace std;// Function to return the result of// the gamestring gameMax(string S){ // length of the string int N = S.length(); // List to maintain the lengths of // consecutive '1's in the string vector<int> list; // Variable that keeps a track of // the current length of the block // of consecutive '1's int one = 0; for(int i = 0; i < N; i++) { if (S[i] == '1') { one++; } else { // Adds non-zero lengths if (one != 0) { list.push_back(one); } one = 0; } } // This takes care of the case // when the last character is '1' if (one != 0) { list.push_back(one); } // Sorts the lengths in // descending order sort(list.begin(), list.end(), greater<int>()); // Scores of the 2 players int score_1 = 0, score_2 = 0; for(int i = 0; i < list.size(); i++) { // For player 1 if (list[i] % 2 == 1) { score_1 += list[i]; } // For player 2 else { score_2 += list[i]; } } // In case of a tie if (score_1 == score_2) return "-1"; // Print the result return (score_1 > score_2) ? "Player 1" : "Player 2";}// Driver Codeint main(){ // Given string S string S = "11111101"; // Function call cout << gameMax(S);}// This code is contributed by rutvik_56 |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG { // Function to return the result of // the game public static String gameMax(String S) { // length of the string int N = S.length(); // List to maintain the lengths of // consecutive '1's in the string List<Integer> list = new ArrayList<>(); // Variable that keeps a track of // the current length of the block // of consecutive '1's int one = 0; for (int i = 0; i < N; i++) { if (S.charAt(i) == '1') { one++; } else { // Adds non-zero lengths if (one != 0) { list.add(one); } one = 0; } } // This takes care of the case // when the last character is '1' if (one != 0) { list.add(one); } // Sorts the lengths in // descending order Collections.sort(list, Collections.reverseOrder()); // Scores of the 2 players int score_1 = 0, score_2 = 0; for (int i = 0; i < list.size(); i++) { // For player 1 if (list.get(i) % 2 == 1) { score_1 += list.get(i); } // For player 2 else { score_2 += list.get(i); } } // In case of a tie if (score_1 == score_2) return "-1"; // Print the result return (score_1 > score_2) ? "Player 1" : "Player 2"; } // Driver Code public static void main(String[] args) { // Given string S String S = "11111101"; // Function Call System.out.println(gameMax(S)); }} |
Python3
# Python3 program for # the above approach # Function to return the # result of the gamedef gameMax(S): # Length of the string N = len(S) # List to maintain the lengths of # consecutive '1's in the string list = [] # Variable that keeps a track of # the current length of the block # of consecutive '1's one = 0 for i in range(N): if(S[i] == '1'): one += 1 else: # Adds non-zero lengths if(one != 0): list.append(one) one = 0 # This takes care of the case # when the last character is '1' if(one != 0): list.append(one) # Sorts the lengths in # descending order list.sort(reverse = True) # Scores of the 2 players score_1 = 0 score_2 = 0 for i in range(len(list)): # For player 1 if(list[i] % 2 == 1): score_1 += list[i] # For player 2 else: score_2 += list[i] # In case of a tie if(score_1 == score_2): return '-1' # Print the result if(score_1 > score_2): return "Player 1" else: return "Player 2"# Driver Code# Given string SS = "11111101"# Function callprint(gameMax(S))# This code is contributed by avanitrachhadiya2155 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to return the result of// the gamepublic static String gameMax(String S){ // length of the string int N = S.Length; // List to maintain the lengths of // consecutive '1's in the string List<int> list = new List<int>(); // Variable that keeps a track of // the current length of the block // of consecutive '1's int one = 0; for(int i = 0; i < N; i++) { if (S[i] == '1') { one++; } else { // Adds non-zero lengths if (one != 0) { list.Add(one); } one = 0; } } // This takes care of the case // when the last character is '1' if (one != 0) { list.Add(one); } // Sorts the lengths in // descending order list.Sort(); list.Reverse(); // Scores of the 2 players int score_1 = 0, score_2 = 0; for(int i = 0; i < list.Count; i++) { // For player 1 if (list[i] % 2 == 1) { score_1 += list[i]; } // For player 2 else { score_2 += list[i]; } } // In case of a tie if (score_1 == score_2) return "-1"; // Print the result return (score_1 > score_2) ? "Player 1" : "Player 2";}// Driver Codepublic static void Main(String[] args){ // Given string S String S = "11111101"; // Function Call Console.WriteLine(gameMax(S));}}// This code is contributed by Amit Katiyar |
Javascript
<script>// javascript program for the// above approach// Function to return the result of// the gamefunction gameMax(S){ // length of the string let N = S.length; // List to maintain the lengths of // consecutive '1's in the string let list = []; // Variable that keeps a track of // the current length of the block // of consecutive '1's let one = 0; for(let i = 0; i < N; i++) { if (S[i] == '1') { one++; } else { // Adds non-zero lengths if (one != 0) { list.push(one); } one = 0; } } // This takes care of the case // when the last character is '1' if (one != 0) { list.push(one); } // Sorts the lengths in // descending order list.sort(); list.reverse(); // Scores of the 2 players let score_1 = 0, score_2 = 0; for(let i = 0; i < list.length; i++) { // For player 1 if (list[i] % 2 == 1) { score_1 += list[i]; } // For player 2 else { score_2 += list[i]; } } // In case of a tie if (score_1 == score_2) return "-1"; // Print the result return (score_1 > score_2) ? "Player 1" : "Player 2";} // Driver Code // Given string S let S = "11111101"; // Function Call document.write(gameMax(S)); // This code is contributed by target_2.</script> |
Output:
Player 2
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!
