Predict the winner of a game by converting 0 to 1 turn by turn following the given rules

Approach

Some key observations are:

• Since a player can only move to its adjacent unoccupied position to play optimally, a player should choose a position with the longest sequence of 0’s on its adjacent sides. Because as long as the player is able to make moves by shifting to the adjacent unoccupied positions, it has better chances to win over the other player.
   
• Player A always starts first, as given in the question. So, to maximise its chances of winning, it will choose the longest sequence of zeroes to start with. So, this guides us to find the longest substring of zeroes in the given array.

It’s time to see the step by step approach to solve this problem.

The steps of the implementation are:

• First, compute the length of the first two longest substrings of zeroes, i.e. the unoccupied positions in the given array present initially before the start of the game.
   
• There will be two cases, i.e. when the length of the longest substring of 0’s is even and the other case when it is odd. Let’s see how we will use this information to find out the winner of the game.
   
• In the first case, when the longest substring of 0’s has an even length, then B will be the winner of the game no matter what is the length of the second-longest substring of 0’s. Why? 
  
  A will always occupy the middle position of the longest substring of 0’s to win. To play optimally, B will occupy the position adjacent to A on the side, having an odd number of zeroes. Now, both A and B will have an equal number of occupied positions on their sides to move. 
  
  Example - Suppose we have an array like this - 10000001 
  In this, the length of the longest substring of 0’s is 6, which is even.
  First A moves and state of the game will be - 1000A001. You can see there are even and odd-sized substrings of 0’s on either side of A. 
  Next, B will occupy the position adjacent to A on the side having an odd number of zeroes like this - 100BA001 
  
  We know that now both have an equal and even number of unoccupied slots available, and A will start to move next. So, the sequence of moves will be - ABAB….(means first A moves, then B, then again A, …), as you can see, since the length of the sequence is, even so, B will always be the last to make a move and after that A will not be able to make any valid moves. Hence, B will be the winner. 
   
• The second case, when the longest substring of 0’s has an odd length. Now, the answer will depend on the length of the second-longest substring of 0’s.
  
  ◾ Let n = length of the longest-substring of 0’s. Then A occupies the middlemost slot and so in total has ceil(n/2) slots to move.  
  
  ◾If the length of the second-longest substring of 0’s is greater than or equal to the number of unoccupied slots available for A to move, then B will win because then B will occupy the second-longest substring of 0’s.
  
  ◾In the other case, when the length of the second-longest substring of 0’s is smaller than ceil(n/2), then A will win as clearly it can make more moves than B. 
   
• So, we will check the above conditions to determine the winner of the game.

Let’s see the code implementation and the time and space complexity analysis in the next section.

Also check out - Substr C++

C++ Implementation

/*C++ code to Predict the winner of a game by converting 0 to 1 turn
by turn following the given rules*/
#include <bits/stdc++.h>
using namespace std;


string predict_winner_ofGame(string s)
{
    int n = s.length();
    int longest = 0, SecondLongest = 0;
    int currLength = 0;


    for (int i = 0; i < n; i++)
    {
        if (s[i] == '0')
        {
            currLength++;
        }
        else
        {
            if (longest <= currLength)
            {
                SecondLongest = longest;
                longest = currLength;
            }
            else if ((currLength < longest) && (currLength > SecondLongest))
            {
                SecondLongest = currLength;
            }


            currLength = 0;
        }
    }
    if (currLength > 0)
    {
        if (longest <= currLength)
        {
            SecondLongest = longest;
            longest = currLength;
        }
        else if ((currLength < longest) && (currLength > SecondLongest))
        {
            SecondLongest = currLength;
        }
    }


    if (longest % 2 == 0)
    {
        return "B";
    }


    int slotsForA = ceil((float)longest / 2);


    if (slotsForA > SecondLongest)
    {
        return "A";
    }


    return "B";
}


int main()
{
    string s = "1000001001";
    string winner = predict_winner_ofGame(s);
    cout << "The winner of the game is: " << winner << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Output

The winner of the game is: A

Time Complexity

O(n), where n = length of the given string. We iterate over the entire string only once to find the length of the two longest substrings of 0’s.

Space Complexity 

O(1), as we don't use any auxiliary space in the approach.

Frequently Asked Questions

1. What is game theory?
   Game Theory is a topic in competitive programming that helps us predict the result of a game without playing the game. In this process, generally, two players are playing the game, and we have to predict as fast as possible which player will win by applying some math behind it.
    
2. Where to find more such interesting concepts and problems in game theory?
   Check out the set of blogs related to Game theory concepts on Coding Ninjas Studio.

Key Takeaways

In this article, we discussed an interesting problem to predict the winner of a game by converting 0 to 1 turn by turn following the given rules. Initially, we started with a vague idea, then we worked on examples and tried to simulate the game. We reached the conclusion that dividing the problem into certain cases can help us determine the winner of the game. 

To solve such problems, you can take some examples and jot down the observations to reach a conclusion.

To check out more such topics in competitive programming, check out Miscellaneous on Coding Ninjas Studio.

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!