Find winner in the game of Binary Array
Given a binary array X[] of size N. Two players A and B are playing games having the following rules, then the task is to determine the winner if B starts first and both players play optimally. The rules are:
- In the first turn, a player selects any index i (1 ≤ i ≤ N) such that A[i] = 0.
- After their first move, a player can choose an index, which is just adjacent to the previously selected index, and the element at that index is also 0.
- After selecting any index, The element is changed to 1 in X[].
- The player which can’t make any move loses the game.
Examples:
Input: N = 7, X[] = {1, 0, 1, 1, 1, 0, 0}
Output: A
Explanation: The moves of the games by both players are as follows:
- Player B: Selects A[ 7 ] = 0. Now update A[ 7 ] = 1.
- Player A: Selects A[ 6 ] = 0. Now update A[ 6 ] = 1.
Now, player B can”t make any move because there is no adjacent index, such that the element at that index is equal to 0.
Input: N = 8, X[] = {1, 1, 0, 0, 0, 0, 0, 1}
Output: B
Explanation: The moves of the game are as follows:
- Player B: Selects A[5]=0. Now update A[5]=1.
- Player A: Selects A[4]=0. Now update A[4]=1.
- Player B: Selects A[6]=0. Now update A[6]=1.
- Player A: Selects A[3]=0. Now update A[3]=1.
- Player B: Selects A[7]=0. Now update A[7]=1.
Now, player A can’t make any move because there is no adjacent index, such that the element at that index is equal to 0.
Approach: The problem is based on the Greedy approach.
Iterate through the array a[] and calculate the maximum frequency of consecutive zeros seen so far and store in variable maxc1 and calculate the second maximum frequency of consecutive zeros seen so far and store in variable maxc2. Now check if the maximum frequency maxc1 is odd and the second maximum frequency maxc2 is strictly less than (maxc1+1)/2, player “B” wins, else player “A” wins.
Steps were taken to solve the problem:
- Count the Number of Consecutive zeros in the array.
- Iterate through the array X[] and count the maximum frequency of consecutive zeros and the second maximum frequency of consecutive zeros and store them in maxc1 and maxc2 respectively.
- Check if the last element of X[] is zero and update the maximum frequency variables if necessary.
- Check if maxc1 is odd and maxc2 is strictly less than (maxc1+1)/2, player “B” wins, else player “A” wins.
Below is the code to implement the approach:
C++14
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to find winner string findWinner( int n, int a[]) { int count = 0; int maxc1 = 0, maxc2 = 0; for ( int i = 0; i < n; i++) { if (a[i]) { if (count > maxc2) { maxc2 = count; if (count > maxc1) { maxc2 = maxc1; maxc1 = count; } } count = 0; } else { count++; } } if (a[n - 1] == 0) { if (count > maxc2) { maxc2 = count; if (count > maxc1) { maxc2 = maxc1; maxc1 = count; } } } if ((maxc1 & 1) and (maxc2 < (maxc1 + 1) / 2)) { return "A" ; } else { return "B" ; } } // Drivers code int main() { int n = 8; int a[8] = { 1, 1, 0, 0, 0, 0, 0, 1 }; // Function call cout << findWinner(n, a); return 0; } |
Java
import java.util.Arrays; public class GFG { // Function to find winner public static String findWinner( int n, int [] a) { int count = 0 ; int maxc1 = 0 , maxc2 = 0 ; for ( int i = 0 ; i < n; i++) { if (a[i] != 0 ) { if (count > maxc2) { // Update the second maximum count maxc2 = count; if (count > maxc1) { // Update the maximum count maxc2 = maxc1; maxc1 = count; } } count = 0 ; } else { // Increment the count of consecutive zeros count++; } } if (a[n - 1 ] == 0 ) { if (count > maxc2) { // Update the second maximum count maxc2 = count; if (count > maxc1) { // Update the maximum count maxc2 = maxc1; maxc1 = count; } } } // Check the conditions and return the winner if ((maxc1 & 1 ) != 0 && (maxc2 < (maxc1 + 1 ) / 2 )) { return "A" ; } else { return "B" ; } } public static void main(String[] args) { int n = 8 ; int [] a = { 1 , 1 , 0 , 0 , 0 , 0 , 0 , 1 }; // Function call System.out.println(findWinner(n, a)); } } |
Python3
# Function to find winner def findWinner(n, a): count = 0 maxc1 = 0 maxc2 = 0 for i in range (n): if a[i]: if count > maxc2: maxc2 = count if count > maxc1: maxc2 = maxc1 maxc1 = count count = 0 else : count + = 1 if a[n - 1 ] = = 0 : if count > maxc2: maxc2 = count if count > maxc1: maxc2 = maxc1 maxc1 = count if (maxc1 & 1 ) and (maxc2 < (maxc1 + 1 ) / / 2 ): return "A" else : return "B" n = 8 a = [ 1 , 1 , 0 , 0 , 0 , 0 , 0 , 1 ] # Function call print (findWinner(n, a)) |
C#
// C# code for the above approach: using System; class GFG { static string FindWinner( int n, int [] a) { int count = 0; int maxc1 = 0, maxc2 = 0; for ( int i = 0; i < n; i++) { if (a[i] == 1) { if (count > maxc2) { // Update the second maximum count maxc2 = count; if (count > maxc1) { // Update the maximum count maxc2 = maxc1; maxc1 = count; } } count = 0; } else { // Increment the count of consecutive zeros count++; } } if (a[n - 1] == 0) { if (count > maxc2) { // Update the second maximum count maxc2 = count; if (count > maxc1) { // Update the maximum count maxc2 = maxc1; maxc1 = count; } } } // Check the conditions and return the winner if ((maxc1 % 2 != 0) || (maxc2 < (maxc1 + 1) / 2)) { return "A" ; } else { return "B" ; } } static void Main() { int n = 8; int [] a = { 1, 1, 0, 0, 0, 0, 0, 1 }; // Function call Console.WriteLine(FindWinner(n, a)); } } |
Javascript
// Function to find winner const findWinner = (n, a) => { let count = 0; let maxc1 = 0; let maxc2 = 0; for (let i = 0; i < n; i++) { if (a[i]) { if (count > maxc2) { maxc2 = count; if (count > maxc1) { maxc2 = maxc1; maxc1 = count; } } count = 0; } else { count += 1; } } if (a[n - 1] === 0) { if (count > maxc2) { maxc2 = count; if (count > maxc1) { maxc2 = maxc1; maxc1 = count; } } } if ((maxc1 & 1) && (maxc2 < (maxc1 + 1) / 2)) { return "A" ; } else { return "B" ; } }; const n = 8; const a = [1, 1, 0, 0, 0, 0, 0, 1]; // Function call console.log(findWinner(n, a)); |
A
Time Complexity: O(N)
Auxiliary Space: O(N), As a vector is used to store adjacent frequencies of zeros.