Given an array arr[] of size N, the task is to find the winner of the game when two players play the game optimally as per the following rules:
- Player 1 starts the game.
- In each turn, a player removes an element from the array.
- Player 2 will win the game only if GCD of all the elements removed by Player 1 becomes equal to 1.
Examples:
Input: arr[] = { 2, 4, 8 }
Output: Player 1
Explanation:
Turn 1: Player 1 removes arr[0]. Therefore, GCD of elements removed by Player 1 = 2
Turn 2: Since GCD of elements removed by Player 1 not equal to 1. Therefore, Player 2 removes arr[1].
Turn 3: Player 1 removes arr[2]. Therefore, GCD of elements removed by Player 1 = GCD(2, 8) = 2
Since the GCD of elements removed by player 1 is not equal to 1, Player 1 wins the game.Input: arr[] = { 2, 1, 1, 1, 1, 1 }
Output: Player 2
Turn 1: Player 1 removes arr[0]. Therefore, GCD of elements removed by Player 1 = 2
Turn 2: Since GCD of elements removed by Player 1 not equal to 1, Player 2 removes arr[1].
Turn 3: Player 1 removes arr[2]. Therefore, GCD of elements removed by Player 1 = GCD(2, 1) = 1
Since GCD of elements removed by player 1 is 1, Player 2 wins the game.
Approach: The optimal way for Player 1 and Player 2 is to always remove the array elements which have at least one common prime factor in most of the array elements. Follow the steps below to solve the problem:
- Initialize a Map, say mp, such that mp[i] stores the count of array elements whose prime factor is i
- Traverse the map and find the maximum value present in the Map, say maxCnt.
- If N is an odd number and maxCnt is equal to N or if N is an even number and maxCnt ? N – 1, then Player 1 wins the game.
- Otherwise, Player 2 wins the game.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find the winner of the game by// removing array elements whose GCD is 1void findWinnerGameRemoveGCD(int arr[], int n){ // mp[i]: Stores count of array // elements whose prime factor is i unordered_map<int, int> mp; // Traverse the array for (int i = 0; i < n; i++) { // Calculate the prime factors // of arr[i] for (int j = 2; j * j <= arr[i]; j++) { // If arr[i] is divisible by j if (arr[i] % j == 0) { // Update mp[j] mp[j]++; while (arr[i] % j == 0) { // Update arr[i] arr[i] = arr[i] / j; } } } // If arr[i] exceeds 1 if (arr[i] > 1) { mp[arr[i]]++; } } // Stores maximum value // present in the Map int maxCnt = 0; // Traverse the map for (auto i : mp) { // Update maxCnt maxCnt = max(maxCnt, i.second); } // If n is an even number if (n % 2 == 0) { // If maxCnt is greater // than or equal to n-1 if (maxCnt >= n - 1) { // Player 1 wins cout << "Player 1"; } else { // Player 2 wins cout << "Player 2"; } } else { // If maxCnt equal to n if (maxCnt == n) { // Player 1 wins cout << "Player 1"; } else { // Player 2 wins cout << "Player 2"; } }}// Driver Codeint main(){ int arr[] = { 2, 4, 8 }; int N = sizeof(arr) / sizeof(arr[0]); findWinnerGameRemoveGCD(arr, N); return 0;} |
Java
// Java program to implement // the above approach import java.util.*;class GFG{ // Function to find the winner of the game by // removing array elements whose GCD is 1 static void findWinnerGameRemoveGCD(int arr[], int n) { // mp[i]: Stores count of array // elements whose prime factor is i HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); // Traverse the array for (int i = 0; i < n; i++) { // Calculate the prime factors // of arr[i] for (int j = 2; j * j <= arr[i]; j++) { // If arr[i] is divisible by j if (arr[i] % j == 0) { // Update mp[j] if (mp.containsKey(j)) { mp.put(j, mp.get(j) + 1); } else { mp.put(j, 1); } while (arr[i] % j == 0) { // Update arr[i] arr[i] = arr[i] / j; } } } // If arr[i] exceeds 1 if (arr[i] > 1) { if(mp.containsKey(arr[i])) { mp.put(arr[i], mp.get(arr[i]) + 1); } else { mp.put(arr[i], 1); } } } // Stores maximum value // present in the Map int maxCnt = 0; // Traverse the map for (Map.Entry<Integer, Integer> i : mp.entrySet()) { // Update maxCnt maxCnt = Math.max(maxCnt, i.getValue()); } // If n is an even number if (n % 2 == 0) { // If maxCnt is greater // than or equal to n-1 if (maxCnt >= n - 1) { // Player 1 wins System.out.print("Player 1"); } else { // Player 2 wins System.out.print("Player 2"); } } else { // If maxCnt equal to n if (maxCnt == n) { // Player 1 wins System.out.print("Player 1"); } else { // Player 2 wins System.out.print("Player 2"); } } } // Driver code public static void main(String[] args) { int arr[] = { 2, 4, 8 }; int N = arr.length; findWinnerGameRemoveGCD(arr, N); }}// This code is contributed by susmitakundugoaldanga |
Python3
# Python3 program to implement# the above approach# Function to find the winner of the game by# removing array elements whose GCD is 1def findWinnerGameRemoveGCD(arr, n) : # mp[i]: Stores count of array # elements whose prime factor is i mp = dict.fromkeys(arr, 0); # Traverse the array for i in range(n) : # Calculate the prime factors # of arr[i] for j in range(2, int(arr[i] * (1/2)) + 1) : # If arr[i] is divisible by j if (arr[i] % j == 0) : # Update mp[j] mp[j] += 1; while (arr[i] % j == 0) : # Update arr[i] arr[i] = arr[i] // j; # If arr[i] exceeds 1 if (arr[i] > 1) : mp[arr[i]] += 1; # Stores maximum value # present in the Map maxCnt = 0; # Traverse the map for i in mp: # Update maxCnt maxCnt = max(maxCnt,mp[i]); # If n is an even number if (n % 2 == 0) : # If maxCnt is greater # than or equal to n-1 if (maxCnt >= n - 1) : # Player 1 wins print("Player 1",end=""); else : # Player 2 wins print("Player 2",end=""); else : # If maxCnt equal to n if (maxCnt == n) : # Player 1 wins print("Player 1",end=""); else : # Player 2 wins print("Player 2",end="");# Driver Codeif __name__ == "__main__" : arr = [ 2, 4, 8 ]; N = len(arr); findWinnerGameRemoveGCD(arr, N); # This code is contributed by AnkThon |
C#
// C# program to implement // the above approach using System;using System.Collections.Generic;class GFG{ // Function to find the winner of the game by // removing array elements whose GCD is 1 static void findWinnerGameRemoveGCD(int []arr, int n) { // mp[i]: Stores count of array // elements whose prime factor is i Dictionary<int, int> mp = new Dictionary<int, int>(); // Traverse the array for (int i = 0; i < n; i++) { // Calculate the prime factors // of arr[i] for (int j = 2; j * j <= arr[i]; j++) { // If arr[i] is divisible by j if (arr[i] % j == 0) { // Update mp[j] if (mp.ContainsKey(j)) { mp[j] = mp[j] + 1; } else { mp.Add(j, 1); } while (arr[i] % j == 0) { // Update arr[i] arr[i] = arr[i] / j; } } } // If arr[i] exceeds 1 if (arr[i] > 1) { if(mp.ContainsKey(arr[i])) { mp[arr[i]] = mp[arr[i]] + 1; } else { mp.Add(arr[i], 1); } } } // Stores maximum value // present in the Map int maxCnt = 0; // Traverse the map foreach (KeyValuePair<int, int> i in mp) { // Update maxCnt maxCnt = Math.Max(maxCnt, i.Value); } // If n is an even number if (n % 2 == 0) { // If maxCnt is greater // than or equal to n-1 if (maxCnt >= n - 1) { // Player 1 wins Console.Write("Player 1"); } else { // Player 2 wins Console.Write("Player 2"); } } else { // If maxCnt equal to n if (maxCnt == n) { // Player 1 wins Console.Write("Player 1"); } else { // Player 2 wins Console.Write("Player 2"); } } } // Driver code public static void Main(String[] args) { int []arr = { 2, 4, 8 }; int N = arr.Length; findWinnerGameRemoveGCD(arr, N); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript program to implement// the above approach// Function to find the winner of the game by// removing array elements whose GCD is 1function findWinnerGameRemoveGCD(arr, n){ // mp[i]: Stores count of array // elements whose prime factor is i let mp = new Map(); // Traverse the array for (let i = 0; i < n; i++) { // Calculate the prime factors // of arr[i] for (let j = 2; j * j <= arr[i];j++) { // If arr[i] is divisible by j if (arr[i] % j == 0) { // Update mp[j] if(mp.has(j)){ mp.set(j,mp.get(j)+1); } else mp.set(j,1); while (arr[i] % j == 0) { // Update arr[i] arr[i] = Math.floor(arr[i] / j); } } } // If arr[i] exceeds 1 if (arr[i] > 1) { if(mp.has(arr[i])){ mp.set(arr[i],mp.get(arr[i])+1); } else mp.set(arr[i],1); } } // Stores maximum value // present in the Map let maxCnt = 0; // Traverse the map for (let [i,j] of mp) { // Update maxCnt maxCnt = Math.max(maxCnt,j); } // If n is an even number if (n % 2 == 0) { // If maxCnt is greater // than or equal to n-1 if (maxCnt >= n - 1) { // Player 1 wins document.write("Player 1"); } else { // Player 2 wins document.write("Player 2"); } } else { // If maxCnt equal to n if (maxCnt == n) { // Player 1 wins document.write("Player 1"); } else { // Player 2 wins document.write("Player 2"); } }}// Driver Codelet arr = [ 2, 4, 8 ];let N = arr.length;findWinnerGameRemoveGCD(arr, N);// This code is contributed by shinjanpatra</script> |
Output:
Player 1
Time Complexity: (N * sqrt(X)), where X is the largest element of the array
Auxiliary Space: O(N)
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!
