Find the winner in game of rotated Array
Given a circular connected binary array X[] of length N. Considered two players A and B are playing the game on the following move:
- Choose a sub-array and left-rotate it once. The move is said to be valid if and only if the number of adjacent indices in X[] having different values (after rotation) is strictly greater than the number of adjacent indices in X[] having different values (before rotation).
- Then the task is to output the winner If player A starts first and both players play optimally.
Examples:
Input: N = 5, X[] = {1, 1, 0, 0, 1}
Output: A
Explanation: The moves of the game are as follows:
- Initially X[] has 2 index such that Xi != Xi+1 Which are 2 and 4. Formally, X2 != X3 and X4 != X5 . It should be noted that X[] is circular connected, Which means X1 and X5 are also adjacent but not different in values.
- Player A chose sub-array {X2, . . . X3} and left rotate it once, Now updated X[] is: {1, 0, 1, 0, 1}. It can be seen that updated X[] has now 4 index such that Xi != Xi+1, Which are 1, 2, 3 and 4. Formally, X1 != X2, X2 != X3, X3 != X4 and X4 != X5 . As in updated X[] such number of indices(4) are greater than the number of indices(2) before rotation, Therefore, the move is valid. Now it can be verify that it is not possible for player B to increase more such indices by performing given move on updated X[]. Hence player A wins the game.
Input: N = 6, X[] = {1, 0, 1, 0, 1, 1}
Output: B
Explanation: It can be verified that if both the player plays optimally, Then it is not possible to win for player A. Therefore, player B wins.
Approach: Implement the idea below to solve the problem:
The problem is based on Game Theory and some observations and can be solve by using those observations by a code.
Steps were taken to solve the problem:
- Create variables count1 and count0 and initialize them to 0.
- Run a loop from 1 to N and follow below-mentioned steps under the scope of loop:
- If X[ i ] == 1 then increment count1 else increment count0.
- Create a variable CurrDiff and initialize it with the number of adjacent indices having different values by traversing X[].
- Create a variable temp.
- If (count0 > count1) then initialize temp as (2 * count1) else (2 * count0).
- Create and Initialize a variable D = (temp – CurrDiff) / 2.
- If D is even then B wins else A wins.
Below is the code to implement the approach:
C++
#include <iostream> using namespace std; // Function for counting adjacent indices // having different values in X[] int Currdiff( int arr[], int N) { int ans = 0; for ( int i = 0; i < N - 1; i++) { if (arr[i] != arr[i + 1]) { ans++; } } if (arr[N - 1] != arr[0]) { ans++; } return ans; } // Function for output the winner // and to implement the approach void Find_Winner( int X[], int N) { // Variables for counting ones // and zeros in X[] int cnt1 = 0; int cnt0 = 0; // Loop for traversing X[] and // initialize cnt1 and cnt0 for ( int i = 0; i < N; i++) { if (X[i] == 1) { cnt1++; } else { cnt0++; } } // Implementation of approach int currDiff = Currdiff(X, N); int temp = 0; if (cnt0 > cnt1) { temp = 2 * cnt1; } else { temp = 2 * cnt0; } int d = (temp - currDiff) / 2; // Printing output if (d % 2 == 0) { cout << "B" << endl; } else { cout << "A" << endl; } } int main() { // inputs int N = 5; int X[] = { 1, 1, 0, 0, 1 }; // Function call for // finding the winner Find_Winner(X, N); return 0; } |
Java
// Java code to implement the approach import java.io.*; import java.lang.*; import java.util.*; class GFG { public static void main(String[] args) throws java.lang.Exception { // inputs int N = 5 ; int X[] = { 1 , 1 , 0 , 0 , 1 }; // Function call for // finding the winner Find_Winner(X, N); } // Function for output the winner // and to implement the approach static void Find_Winner( int [] X, int N) { // Variables for counting ones // and zeros in X[] int cnt1 = 0 ; int cnt0 = 0 ; // Loop for traversing X[] and // initialize cnt1 and cnt0 for ( int i = 0 ; i < N; i++) { if (X[i] == 1 ) { cnt1++; } else { cnt0++; } } // Implementation of approach int currDiff = Currdiff(X); int temp = 0 ; if (cnt0 > cnt1) { temp = 2 * cnt1; } else { temp = 2 * cnt0; } int d = (temp - currDiff) / 2 ; // Printing output if (d % 2 == 0 ) { System.out.println( "B" ); } else { System.out.println( "A" ); } } // Function for counting adjacent // indices having different // values in X[] public static int Currdiff( int arr[]) { int ans = 0 ; for ( int i = 0 ; i < arr.length - 1 ; i++) { if (arr[i] != arr[i + 1 ]) { ans++; } } if (arr[arr.length - 1 ] != arr[ 0 ]) { ans++; } return ans; } } |
Python3
# Function for counting adjacent indices # having different values in X[] def Currdiff(arr, N): ans = 0 for i in range (N - 1 ): if arr[i] ! = arr[i + 1 ]: ans + = 1 if arr[N - 1 ] ! = arr[ 0 ]: ans + = 1 return ans # Function for output the winner # and to implement the approach def Find_Winner(X, N): # Variables for counting ones # and zeros in X[] cnt1 = 0 cnt0 = 0 # Loop for traversing X[] and # initialize cnt1 and cnt0 for i in range (N): if X[i] = = 1 : cnt1 + = 1 else : cnt0 + = 1 # Implementation of approach currDiff = Currdiff(X, N) temp = 0 if cnt0 > cnt1: temp = 2 * cnt1 else : temp = 2 * cnt0 d = (temp - currDiff) / / 2 # Printing output if d % 2 = = 0 : print ( "B" ) else : print ( "A" ) # inputs N = 5 X = [ 1 , 1 , 0 , 0 , 1 ] # Function call for # finding the winner Find_Winner(X, N) # This code is contributed by Prasad Kandekar(prasad264) |
C#
// C# code to implement the approach using System; public class GFG{ // Function for output the winner // and to implement the approach static void Find_Winner( int [] X, int N) { // Variables for counting ones // and zeros in X[] int cnt1 = 0; int cnt0 = 0; // Loop for traversing X[] and // initialize cnt1 and cnt0 for ( int i = 0; i < N; i++) { if (X[i] == 1) { cnt1++; } else { cnt0++; } } // Implementation of approach int currDiff = Currdiff(X); int temp = 0; if (cnt0 > cnt1) { temp = 2 * cnt1; } else { temp = 2 * cnt0; } int d = (temp - currDiff) / 2; // Printing output if (d % 2 == 0) { Console.WriteLine( "B" ); } else { Console.WriteLine( "A" ); } } // Function for counting adjacent // indices having different // values in X[] public static int Currdiff( int [] arr) { int ans = 0; for ( int i = 0; i < arr.Length - 1; i++) { if (arr[i] != arr[i + 1]) { ans++; } } if (arr[arr.Length - 1] != arr[0]) { ans++; } return ans; } static public void Main (){ // inputs int N = 5; int [] X = { 1, 1, 0, 0, 1 }; // Function call for // finding the winner Find_Winner(X, N); } } |
Javascript
// Javascript code to implement the approach // Function for counting adjacent indices // having different values in X[] function Currdiff(arr, N) { let ans = 0; for (let i = 0; i < N - 1; i++) { if (arr[i] != arr[i + 1]) { ans++; } } if (arr[N - 1] != arr[0]) { ans++; } return ans; } // Function for output the winner // and to implement the approach function Find_Winner(X, N) { // Variables for counting ones // and zeros in X[] let cnt1 = 0; let cnt0 = 0; // Loop for traversing X[] and // initialize cnt1 and cnt0 for (let i = 0; i < N; i++) { if (X[i] == 1) { cnt1++; } else { cnt0++; } } // Implementation of approach let currDiff = Currdiff(X, N); let temp = 0; if (cnt0 > cnt1) { temp = 2 * cnt1; } else { temp = 2 * cnt0; } let d = (temp - currDiff) / 2; // Printing output if (d % 2 == 0) { console.log( "B" ); } else { console.log( "A" ); } } // inputs let N = 5; let X = [ 1, 1, 0, 0, 1 ]; // Function call for // finding the winner Find_Winner(X, N); |
Output
A
Time Complexity: O(N)
Auxiliary Space: O(1)