Given an array arr[] of integers, two players A and B are playing a game where A can remove any number of non-zero elements from the array that are multiples of 3. Similarly, B can remove multiples of 5. The player who can’t remove any element loses the game. The task is to find the winner of the game if A starts first and both play optimally.
Examples:
Input: arr[] = {1, 2, 3, 5, 6}
Output: A
3 and 6 are the elements that A can remove.
5 is the only element that B can remove.
A can remove 3 in his first move then B will have to remove 5. In the next turn, A will remove 6 and B will be left with no more moves to make.
Input: arr[] = {3, 5, 15, 20, 6, 9}
Output: A
Approach: Store the count of elements only divisible by 3 in movesA, count of elements only divisible by 5 in movesB and the elements divisible by both in movesBoth. Now,
- If movesBoth = 0 then both the players can remove only the elements which are divisible by their respective number and A will win the game only when movesA > movesB.
- If movesBoth > 0 then in order to play optimally, A will remove all the elements that are divisible by both 3 and 5 so that B is left with no elements to remove from the common elements then A will be the winner only if movesA + 1 > movesB
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the winner of the game string getWinner( int arr[], int n) { int movesA = 0, movesB = 0, movesBoth = 0; for ( int i = 0; i < n; i++) { // Increment common moves if (arr[i] % 3 == 0 && arr[i] % 5 == 0) movesBoth++; // Increment A's moves else if (arr[i] % 3 == 0) movesA++; // Increment B's moves else if (arr[i] % 5 == 0) movesB++; } // If there are no common moves if (movesBoth == 0) { if (movesA > movesB) return "A" ; return "B" ; } // 1 is added because A can remove all the elements // that are part of the common moves in a single move if (movesA + 1 > movesB) return "A" ; return "B" ; } // Driver code int main() { int arr[] = { 1, 2, 3, 5, 6 }; int n = sizeof (arr) / sizeof (arr[0]); cout << getWinner(arr, n); return 0; } |
Java
// Java implementation of the approach class GfG { // Function to return the winner of the game static String getWinner( int arr[], int n) { int movesA = 0 , movesB = 0 , movesBoth = 0 ; for ( int i = 0 ; i < n; i++) { // Increment common moves if (arr[i] % 3 == 0 && arr[i] % 5 == 0 ) movesBoth++; // Increment A's moves else if (arr[i] % 3 == 0 ) movesA++; // Increment B's moves else if (arr[i] % 5 == 0 ) movesB++; } // If there are no common moves if (movesBoth == 0 ) { if (movesA > movesB) return "A" ; return "B" ; } // 1 is added because A can remove // all the elements that are part // of the common moves in a single move if (movesA + 1 > movesB) return "A" ; return "B" ; } // Driver code public static void main(String []args) { int arr[] = { 1 , 2 , 3 , 5 , 6 }; int n = arr.length; System.out.println(getWinner(arr, n)); } } // This code is contributed by Rituraj Jain |
Python3
# Python3 implementation of the approach # Function to return the winner of the game def getWinner(arr, n): movesA, movesB, movesBoth = 0 , 0 , 0 for i in range ( 0 , n): # Increment common moves if arr[i] % 3 = = 0 and arr[i] % 5 = = 0 : movesBoth + = 1 # Increment A's moves elif arr[i] % 3 = = 0 : movesA + = 1 # Increment B's moves elif arr[i] % 5 = = 0 : movesB + = 1 # If there are no common moves if movesBoth = = 0 : if movesA > movesB: return "A" return "B" # 1 is added because A can # remove all the elements # that are part of the common # moves in a single move if movesA + 1 > movesB: return "A" return "B" # Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 5 , 6 ] n = len (arr) print (getWinner(arr, n)) # This code is contributed by Rituraj Jain |
C#
// C# implementation of the approach using System; class GfG { // Function to return the winner of the game static String getWinner( int []arr, int n) { int movesA = 0, movesB = 0, movesBoth = 0; for ( int i = 0; i < n; i++) { // Increment common moves if (arr[i] % 3 == 0 && arr[i] % 5 == 0) movesBoth++; // Increment A's moves else if (arr[i] % 3 == 0) movesA++; // Increment B's moves else if (arr[i] % 5 == 0) movesB++; } // If there are no common moves if (movesBoth == 0) { if (movesA > movesB) return "A" ; return "B" ; } // 1 is added because A can remove // all the elements that are part // of the common moves in a single move if (movesA + 1 > movesB) return "A" ; return "B" ; } // Driver code public static void Main(String []args) { int []arr = { 1, 2, 3, 5, 6 }; int n = arr.Length; Console.WriteLine(getWinner(arr, n)); } } // This code is contributed by // Rajput-Ji |
PHP
<?php // PHP implementation of the approach // Function to return the winner of the game function getWinner( $arr , $n ) { $movesA = 0; $movesB = 0; $movesBoth = 0; for ( $i = 0; $i < $n ; $i ++) { // Increment common moves if ( $arr [ $i ] % 3 == 0 && $arr [ $i ] % 5 == 0) $movesBoth ++; // Increment A's moves else if ( $arr [ $i ] % 3 == 0) $movesA ++; // Increment B's moves else if ( $arr [ $i ] % 5 == 0) $movesB ++; } // If there are no common moves if ( $movesBoth == 0) { if ( $movesA > $movesB ) return "A" ; return "B" ; } // 1 is added because A can remove all the elements // that are part of the common moves in a single move if ( $movesA + 1 > $movesB ) return "A" ; return "B" ; } // Driver code $arr = array ( 1, 2, 3, 5, 6 ); $n = sizeof( $arr ) / sizeof( $arr [0]); echo getWinner( $arr , $n ); // This code is contributed by ajit. ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the winner of the game function getWinner(arr, n) { let movesA = 0, movesB = 0, movesBoth = 0; for (let i = 0; i < n; i++) { // Increment common moves if (arr[i] % 3 == 0 && arr[i] % 5 == 0) movesBoth++; // Increment A's moves else if (arr[i] % 3 == 0) movesA++; // Increment B's moves else if (arr[i] % 5 == 0) movesB++; } // If there are no common moves if (movesBoth == 0) { if (movesA > movesB) return "A" ; return "B" ; } // 1 is added because A can // remove all the elements // that are part of the common // moves in a single move if (movesA + 1 > movesB) return "A" ; return "B" ; } // Driver code let arr = [ 1, 2, 3, 5, 6 ]; let n = arr.length; document.write(getWinner(arr, n)); </script> |
A
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!