Find the winner of game of removing array elements having GCD equal to 1 | 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
def findWinnerGameRemoveGCD ( arr , n ) : NEW_LINE INDENT mp = dict . fromkeys ( arr , 0 ) ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( 2 , int ( arr [ i ] * ( 1 / 2 ) ) + 1 ) : NEW_LINE INDENT if ( arr [ i ] % j == 0 ) : NEW_LINE INDENT mp [ j ] += 1 ; NEW_LINE while ( arr [ i ] % j == 0 ) : NEW_LINE INDENT arr [ i ] = arr [ i ] // j ; NEW_LINE DEDENT DEDENT DEDENT if ( arr [ i ] > 1 ) : NEW_LINE INDENT mp [ arr [ i ] ] += 1 ; NEW_LINE DEDENT DEDENT maxCnt = 0 ; NEW_LINE for i in mp : NEW_LINE INDENT maxCnt = max ( maxCnt , mp [ i ] ) ; NEW_LINE DEDENT if ( n % 2 == 0 ) : NEW_LINE INDENT if ( maxCnt >= n - 1 ) : NEW_LINE INDENT print ( " Player ▁ 1" , end = " " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Player ▁ 2" , end = " " ) ; NEW_LINE DEDENT DEDENT else : NEW_LINE INDENT if ( maxCnt == n ) : NEW_LINE INDENT print ( " Player ▁ 1" , end = " " ) ; NEW_LINE DEDENT else : NEW_LINE INDENT print ( " Player ▁ 2" , end = " " ) ; NEW_LINE DEDENT DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 2 , 4 , 8 ] ; NEW_LINE N = len ( arr ) ; NEW_LINE findWinnerGameRemoveGCD ( arr , N ) ; NEW_LINE DEDENT