Given an array arr[] consisting of N integers and two players A and B playing a game together by performing the following operations:
- Choose an integer from arr[] and replace that number with one of its divisors.
- A previously selected integer cannot be chosen again.
- As 1 does not have any divisor other than itself, a player cannot replace 1 with any other number. Hence, when the array consists of only 1s, the player who cannot make any move loses the game.
- Both the players will play optimally and A makes the first move of the game.
The task is to find the winner of the game.
Examples:
Input: arr[] = {24, 45, 45, 24}
Output: B
Explanation:
Player A replaces 24 in the first index with 1. Since, 1 is a divisor of 24. arr[] = {1, 45, 45, 24}
Player B replaces 24 in the last index with 1. Since, 1 is a divisor of 24. arr[] = {1, 45, 45, 1}
Player A replaces 45 in the second index with 1. Since, 1 is a divisor of 45. arr[] = {1, 1, 45, 24}
Player B replaces 45 in the third index with 1. Since, 1 is a divisor of 45. arr[] = {1, 1, 1, 1}
Player A cannot make a move now, since all elements are 1. Therefore, player B wins the game.Input: arr[] = {18, 6}
Output: B
Approach: The problem can be solved based on a simple observation:
- Since 1 is a divisor of all any integers, hence, replace every array element with 1 in each operation.
- Therefore, if the array consists of a even number of elements, then player B wins.
- Otherwise, player A wins.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the winner// of the game played based on// given conditionsvoid winner(int arr[], int N){ // A wins if size of array is odd if (N % 2 == 1) { cout << "A"; } // Otherwise, B wins else { cout << "B"; }}// Driver Codeint main(){ // Input array int arr[] = { 24, 45, 45, 24 }; // Size of the array int N = sizeof(arr) / sizeof(arr[0]); winner(arr, N);} |
Java
// Java program for the above approachclass GFG{// Function to find the winner// of the game played based on// given conditionsstatic void winner(int arr[], int N){ // A wins if size of array is odd if (N % 2 == 1) { System.out.print("A"); } // Otherwise, B wins else { System.out.print("B"); }}// Driver Codepublic static void main(String[] args){ // Input array int arr[] = { 24, 45, 45, 24 }; // Size of the array int N = arr.length; winner(arr, N);}}// This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach# Function to find the winner# of the game played based on# given conditionsdef winner(arr, N): # A wins if size of array is odd if (N % 2 == 1): print ("A") # Otherwise, B wins else: print ("B")# Driver Codeif __name__ == '__main__': # Input array arr = [24, 45, 45, 24] # Size of the array N = len(arr) winner(arr, N) # This code is contributed by mohit kumar 29. |
C#
// C# program for the above approachusing System;public class GFG{// Function to find the winner// of the game played based on// given conditionsstatic void winner(int []arr, int N){ // A wins if size of array is odd if (N % 2 == 1) { Console.Write("A"); } // Otherwise, B wins else { Console.Write("B"); }}// Driver Codepublic static void Main(String[] args){ // Input array int []arr = { 24, 45, 45, 24 }; // Size of the array int N = arr.Length; winner(arr, N);}}// This code contributed by shikhasingrajput |
Javascript
<script> // JavaScript program for the above approach // Function to find the winner // of the game played based on // given conditions function winner(arr, N) { // A wins if size of array is odd if (N % 2 === 1) { document.write("A"); } // Otherwise, B wins else { document.write("B"); } } // Driver Code // Input array var arr = [24, 45, 45, 24]; // Size of the array var N = arr.length; winner(arr, N); // This code is contributed by rdtank. </script> |
B
Time Complexity: O(N), where N is the size of the array.
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
