Find the winner of game of removing array elements having GCD equal to 1 | Java 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
import java . util . * ; class GFG { static void findWinnerGameRemoveGCD ( int arr [ ] , int n ) { HashMap < Integer , Integer > mp = new HashMap < Integer , Integer > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 2 ; j * j <= arr [ i ] ; j ++ ) { if ( arr [ i ] % j == 0 ) { if ( mp . containsKey ( j ) ) { mp . put ( j , mp . get ( j ) + 1 ) ; } else { mp . put ( j , 1 ) ; } while ( arr [ i ] % j == 0 ) { arr [ i ] = arr [ i ] / j ; } } } if ( arr [ i ] > 1 ) { if ( mp . containsKey ( arr [ i ] ) ) { mp . put ( arr [ i ] , mp . get ( arr [ i ] ) + 1 ) ; } else { mp . put ( arr [ i ] , 1 ) ; } } } int maxCnt = 0 ; for ( Map . Entry < Integer , Integer > i : mp . entrySet ( ) ) { maxCnt = Math . max ( maxCnt , i . getValue ( ) ) ; } if ( n % 2 == 0 ) { if ( maxCnt >= n - 1 ) { System . out . print ( " Player ▁ 1" ) ; } else { System . out . print ( " Player ▁ 2" ) ; } } else { if ( maxCnt == n ) { System . out . print ( " Player ▁ 1" ) ; } else { System . out . print ( " Player ▁ 2" ) ; } } } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 4 , 8 } ; int N = arr . length ; findWinnerGameRemoveGCD ( arr , N ) ; } }