Find the winner of game of removing array elements having GCD equal to 1 | C ++ program to implement the above approach ; Function to find the winner of the game by removing array elements whose GCD is 1 ; mp [ i ] : Stores count of array elements whose prime factor is i ; Traverse the array ; Calculate the prime factors of arr [ i ] ; If arr [ i ] is divisible by j ; Update mp [ j ] ; Update arr [ i ] ; If arr [ i ] exceeds 1 ; Stores maximum value present in the Map ; Traverse the map ; Update maxCnt ; If n is an even number ; If maxCnt is greater than or equal to n - 1 ; Player 1 wins ; Player 2 wins ; If maxCnt equal to n ; Player 1 wins ; Player 2 wins ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findWinnerGameRemoveGCD ( int arr [ ] , int n ) { unordered_map < int , int > mp ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 2 ; j * j <= arr [ i ] ; j ++ ) { if ( arr [ i ] % j == 0 ) { mp [ j ] ++ ; while ( arr [ i ] % j == 0 ) { arr [ i ] = arr [ i ] / j ; } } } if ( arr [ i ] > 1 ) { mp [ arr [ i ] ] ++ ; } } int maxCnt = 0 ; for ( auto i : mp ) { maxCnt = max ( maxCnt , i . second ) ; } if ( n % 2 == 0 ) { if ( maxCnt >= n - 1 ) { cout << " Player ▁ 1" ; } else { cout << " Player ▁ 2" ; } } else { if ( maxCnt == n ) { cout << " Player ▁ 1" ; } else { cout << " Player ▁ 2" ; } } } int main ( ) { int arr [ ] = { 2 , 4 , 8 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; findWinnerGameRemoveGCD ( arr , N ) ; return 0 ; }