Given a circular array arr[] of size N containing positive integers only, Player A and B are playing a game, turn by turn, the game will start with player A at index 0 and then player B at the next index.
- In every turn a player can deduct some value from arr[i] and decrease the value of an element arr[i] to X ( 0 to arr[i]-1 ).
- Then, other player turn will come and he/she will do the same with the next element in right circular order.
If a player cannot decrease the value of the element then he/she loses. Find if A and B play optimally, who will win?
Note: In each turn, a player moves to a new position than his/her previous position.
Examples:
Input: arr[] = {1, 2, 4, 3}
Output: B
Explanation: A have to deduct 1 from 1,
Now it’s B turn, B deduct whatever from 2,
Again, A deduct whatever from index 3,
Again, B deduct whatever from index 4,
Now, it’s A turn, and A is on index 0, and index 0th element is 0.
So, A will lose, B win.Input: arr[] = {5}
Output: A
Explanation: A will decrease the value of arr[i]( 5 ) to 0.
So, for B the number become 0 and B will lose, A win.
Approach: To solve the problem follow the below idea:
The idea is, A only remove some amount from even indexed integers and B only remove some amount from odd indexed integers.
If N = odd, A will always win because
- A will remove all the amount from index 0 element making the number = 0,
- Now the other numbers whatever maybe and whatever amount will both of them remove from them, the thing is, B will always come to 0th indexed element i.e., 0, after one rotation, So, B will lose for sure,
But for N = Even, we check in what position the minimum element occur, even or odd, because
- The optimal strategy is that every one remove 1 unit from their parity element.
- And in whichever parity the first time minimum element will occur that parity element will become 0 for the first time and the player will lose and other parity element will win.
Follow the below steps to solve the problem:
- If N is Odd, A will win for sure, so just print A.
- Else find position of the first minimum element in the arr[].
- If the position is even A will win.
- Else B will win.
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to find who will win A or Bvoid findAorB(int* arr, int N){ int K, Min = INT_MAX; // If N is odd A will win if (N & 1) cout << "A" << endl; // Else find position of minimum element else { for (int i = 0; i < N; i++) { if (Min > arr[i]) { Min = arr[i]; K = i + 1; } } // If position of Min element is odd // B will win if (K & 1) cout << "B" << endl; // If position of Min element is even // A will win else cout << "A" << endl; }}// Driver Codeint main(){ int arr[] = { 1, 2, 4, 3 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call findAorB(arr, N); return 0;} |
Java
// Java code to implement the above approachimport java.io.*;class GFG { // Function to find who will win A or B public static void findAorB(int arr[], int N) { int K = 0, Min = Integer.MAX_VALUE; // If N is odd A will win if (N % 2 != 0) System.out.println("A"); // Else find position of minimum element else { for (int i = 0; i < N; i++) { if (Min > arr[i]) { Min = arr[i]; K = i + 1; } } // If position of Min element is odd // B will win if (K % 2 != 0) System.out.println("B"); // If position of Min element is even // A will win else System.out.println("A"); } } // Driver Code public static void main(String[] args) { int arr[] = { 1, 2, 4, 3 }; int N = 4; // Function call findAorB(arr, N); }}// This code is contributed by Rohit Pradhan |
Python3
# python3 code to implement the above approachINT_MAX = 2147483647# Function to find who will win A or Bdef findAorB(arr, N): K = 0 Min = INT_MAX # If N is odd A will win if (N & 1): print("A") # Else find position of minimum element else: for i in range(0, N): if (Min > arr[i]): Min = arr[i] K = i + 1 # If position of Min element is odd # B will win if (K & 1): print("B") # If position of Min element is even # A will win else: print("A")# Driver Codeif __name__ == "__main__": arr = [1, 2, 4, 3] N = len(arr) # Function call findAorB(arr, N) # This code is contributed by rakeshsahni |
C#
// C# code to implement the above approachusing System;public class GFG { // Function to find who will win A or B public static void findAorB(int []arr, int N) { int K = 0, Min = int.MaxValue; // If N is odd A will win if (N % 2 != 0) Console.WriteLine("A"); // Else find position of minimum element else { for (int i = 0; i < N; i++) { if (Min > arr[i]) { Min = arr[i]; K = i + 1; } } // If position of Min element is odd // B will win if (K % 2 != 0) Console.WriteLine("B"); // If position of Min element is even // A will win else Console.WriteLine("A"); } } // Driver Code public static void Main(string[] args) { int []arr = { 1, 2, 4, 3 }; int N = 4; // Function call findAorB(arr, N); }}// This code is contributed by AnkThon |
Javascript
<script>// Javascript code to implement the above approach// Function to find who will win A or Bfunction findAorB(arr,N){ let K, Min = Number.MAX_VALUE; // If N is odd A will win if (N & 1) document.write("A" ); // Else find position of minimum element else { for (let i = 0; i < N; i++) { if (Min > arr[i]) { Min = arr[i]; K = i + 1; } } // If position of Min element is odd // B will win if (K & 1) document.write("B"); // If position of Min element is even // A will win else document.write("A"); }}// Driver Code let arr = [ 1, 2, 4, 3 ]; let N = arr.length; // Function call findAorB(arr, N); </script> |
B
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
