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 gamestring 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 codeint 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 approachusing 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 gamefunction 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 gamefunction 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> |
Output:
A
Time Complexity: O(n)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
