Predict the winner of a game by converting 0 to 1 turn by turn following the given rules
Given a binary string str consisting of only 0 and 1, where 0 represent an unoccupied position and 1 represent an occupied position. Two players A and B have to occupy an unoccupied position (convert 0 to 1) turn by turn following the given rules:
- The player can only occupy the unoccupied position
- The player can only move to its adjacent position in every turn
If a player is not able to make a move on the turn he loses. Predict the winner of the game if both play optimally given that A makes the first move.
Example:
Input: str=”1000″
Output: A
Explanation: A makes first move and occupy position at 2nd index of the string(0 based index) then no matter which position B choose there will be only a single unoccupied position left which will be occupied by A in next turn and B can’t make further move hence A wins.Input: str=”1001″
Output: B
Approach:
- Find the length of the two longest substrings of initial unoccupied positions (i.e. substring of 0s).
- If the length of the largest substring is even, then B will be the winner irrespective of the length of the second-largest substring. This is because A will always occupy the middle slot of the largest substring hence in this case it will have the same number of slots for the move as left for B in the given substring. A needs more slots than B to win the game, while in this case, both have an equal number of slots hence A will lose.
- If the length of the largest substring is odd then there can be two cases:
- If the length of the second-largest substring is less than the number of slots of A in the largest substring (i.e. (n/2) + 1 where n is the size of the substring) then A will be the winner since B will always have a lesser number of slots to than A irrespective of his initial decision (to choose between largest or second-largest substring).
- Else, B will be the winner as B can choose the second-largest substring to make the initial move and will have more slots available for further moves than A.
- Print the answer according to the above observation.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> #include <math.h> using namespace std; // Function to predict the winner string predictWinner(string s) { int n = s.length(); int max1 = 0, max2 = 0; int curr = 0; // Loop through the string to find out // lengths of longest two substrings of 0s for ( int i = 0; i < n; i++) { if (s[i] == '0' ) { curr++; } else { if (max1 <= curr) { max2 = max1; max1 = curr; } else if ((curr < max1) && (curr > max2)) { max2 = curr; } curr = 0; } } if (curr > 0) { if (max1 <= curr) { max2 = max1; max1 = curr; } else if ((curr < max1) && (curr > max2)) { max2 = curr; } } // If longest substring // of 0s is of even length // then B will always be the winner if (max1 % 2 == 0) { return "B" ; } // Slot for A's moves // will be half the total // number of slots plus // one in longest substring int left = ceil (( float )max1 / 2); // If slots for A's moves // are more than slots in // second largest substring // then A will be the // winner else B will be winner if (left > max2) { return "A" ; } return "B" ; } // Driver Code int main() { string s = "1000" ; string ans = predictWinner(s); cout << ans; return 0; } |
C
// C program for the above approach #include <math.h> #include <stdio.h> // Function to predict the winner char predictWinner( char s[], int n) { int max1 = 0, max2 = 0; int curr = 0; // Loop through the string to find out // lengths of longest two substrings of 0s for ( int i = 0; i < n; i++) { if (s[i] == '0' ) { curr++; } else { if (max1 <= curr) { max2 = max1; max1 = curr; } else if ((curr < max1) && (curr > max2)) { max2 = curr; } curr = 0; } } if (curr > 0) { if (max1 <= curr) { max2 = max1; max1 = curr; } else if ((curr < max1) && (curr > max2)) { max2 = curr; } } // If longest substring // of 0s is of even length // then B will always be the winner if (max1 % 2 == 0) { return 'B' ; } // Slot for A's moves // will be half the total // number of slots plus // one in longest substring int left = ceil (( float )max1 / 2); // If slots for A's moves // are more than slots in // second largest substring // then A will be the // winner else B will be winner if (left > max2) { return 'A' ; } return 'B' ; } // Driver Code int main() { char s[] = "1000" ; int n = 4; char ans = predictWinner(s, n); printf ( "%c" , ans); return 0; } // This code is contributed by saxenaanjali239. |
Java
// Java program for the above approach import java.lang.Math; import java.util.*; public class w3wiki { // Function to predict the winner public static String predictWinner(String s) { int n = s.length(); int max1 = 0 , max2 = 0 ; int curr = 0 ; // Loop through the string to find out // lengths of longest two substrings of 0s for ( int i = 0 ; i < n; i++) { if (s.charAt(i) == '0' ) { curr++; } else { if (max1 <= curr) { max2 = max1; max1 = curr; } else if ((curr < max1) && (curr > max2)) { max2 = curr; } curr = 0 ; } } if (curr > 0 ) { if (max1 <= curr) { max2 = max1; max1 = curr; } else if ((curr < max1) && (curr > max2)) { max2 = curr; } } // If longest substring // of 0s is of even length // then B will always be the winner if (max1 % 2 == 0 ) { return "B" ; } // Slot for A's moves // will be half the total // number of slots plus // one in longest substring int left = ( int )Math.ceil(( float )max1 / 2 ); // If slots for A's moves // are more than slots in // second largest substring // then A will be the // winner else B will be winner if (left > max2) { return "A" ; } return "B" ; } // Driver Code public static void main(String args[]) { String s = "1000" ; String ans = predictWinner(s); System.out.println(ans); } } // This code is contributed by saxenaanjali239. |
Python
# Python program for the above approach import math def predictWinner(s, n): max1 = 0 max2 = 0 curr = 0 i = 0 # Loop through the string to find out # lengths of longest two substrings of 0s for i in range (n): if s[i] = = '0' : curr + = 1 else : if max1 < = curr: max2 = max1 max1 = curr elif (curr < max1) and (curr > max2): max2 = curr curr = 0 if curr > 0 : if max1 < = curr: max2 = max1 max1 = curr elif (curr < max1) and (curr > max2): max2 = curr # If longest substring # of 0s is of even length # then B will always be the winner if max1 % 2 = = 0 : return "B" # Slot for A's moves # will be half the total # number of slots plus # one in longest substring left = math.ceil(max1 / 2 ) # If slots for A's moves # are more than slots in # second largest substring # then A will be the # winner else B will be winner if left > max2: return "A" return "B" # Driver program to test the above function s = "1000" n = len (s) ans = predictWinner(s, n) print (ans) # This code is contributed by saxenaanjali239. |
C#
// C# program for the above approach using System; class w3wiki { // Function to predict the winner static string predictWinner( string s) { int n = s.Length; int max1 = 0, max2 = 0; int curr = 0; // Loop through the string to find out // lengths of longest two substrings of 0s for ( int i = 0; i < n; i++) { if (s[i] == '0' ) { curr++; } else { if (max1 <= curr) { max2 = max1; max1 = curr; } else if ((curr < max1) && (curr > max2)) { max2 = curr; } curr = 0; } } if (curr > 0) { if (max1 <= curr) { max2 = max1; max1 = curr; } else if ((curr < max1) && (curr > max2)) { max2 = curr; } } // If longest substring // of 0s is of even length // then B will always be the winner if (max1 % 2 == 0) { return "B" ; } // Slot for A's moves // will be half the total // number of slots plus // one in longest substring int left = ( int )Math.Ceiling(( float )max1 / 2); // If slots for A's moves // are more than slots in // second largest substring // then A will be the // winner else B will be winner if (left > max2) { return "A" ; } return "B" ; } // Driver Code public static void Main() { string s = "1000" ; string ans = predictWinner(s); Console.Write(ans); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // Javascript program for the above approach // Function to predict the winner function predictWinner(s) { let n = s.length; let max1 = 0, max2 = 0; let curr = 0; // Loop through the string to find out // lengths of longest two substrings of 0s for (let i = 0; i < n; i++) { if (s[i] == '0' ) { curr++; } else { if (max1 <= curr) { max2 = max1; max1 = curr; } else if ((curr < max1) && (curr > max2)) { max2 = curr; } curr = 0; } } if (curr > 0) { if (max1 <= curr) { max2 = max1; max1 = curr; } else if ((curr < max1) && (curr > max2)) { max2 = curr; } } // If longest substring // of 0s is of even length // then B will always be the winner if (max1 % 2 == 0) { return "B" ; } // Slot for A's moves // will be half the total // number of slots plus // one in longest substring let left = Math.ceil(max1 / 2); // If slots for A's moves // are more than slots in // second largest substring // then A will be the // winner else B will be winner if (left > max2) { return "A" ; } return "B" ; } // Driver Code let s = "1000" ; let ans = predictWinner(s); document.write(ans); // This code is contributed by Samim Hossain Mondal. </script> |
A
Time Complexity: O(N)
Auxiliary Space: O(1)