Find the winner of the game based on greater number of divisors | Python3 implementation of the approach ; Function to return the count of divisors of elem ; Function to return the winner of the game ; Convert every element of A [ ] to their divisor count ; Convert every element of B [ ] to their divisor count ; Sort both the arrays ; For every element of A [ ] apply binary search to find number of pairs where A wins ; B wins if A doesnot win ; Driver code
from math import * NEW_LINE def divisorcount ( elem ) : NEW_LINE INDENT ans = 0 NEW_LINE for i in range ( 1 , int ( sqrt ( elem ) ) + 1 ) : NEW_LINE INDENT if ( elem % i == 0 ) : NEW_LINE INDENT if ( i * i == elem ) : NEW_LINE INDENT ans += 1 NEW_LINE DEDENT else : NEW_LINE INDENT ans += 2 NEW_LINE DEDENT DEDENT DEDENT return ans NEW_LINE DEDENT def findwinner ( A , B , N , M ) : NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT A [ i ] = divisorcount ( A [ i ] ) NEW_LINE DEDENT for i in range ( M ) : NEW_LINE INDENT B [ i ] = divisorcount ( B [ i ] ) NEW_LINE DEDENT A . sort ( ) NEW_LINE B . sort ( ) NEW_LINE winA = 0 NEW_LINE for i in range ( N ) : NEW_LINE INDENT val = A [ i ] NEW_LINE start = 0 NEW_LINE end = M - 1 NEW_LINE index = - 1 NEW_LINE while ( start <= end ) : NEW_LINE INDENT mid = ( start + end ) // 2 NEW_LINE if ( B [ mid ] <= val ) : NEW_LINE INDENT index = mid NEW_LINE start = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT end = mid - 1 NEW_LINE DEDENT DEDENT winA += ( index + 1 ) NEW_LINE DEDENT winB = N * M - winA NEW_LINE if ( winA > winB ) : NEW_LINE INDENT return " A " NEW_LINE DEDENT elif ( winB > winA ) : NEW_LINE INDENT return " B " NEW_LINE DEDENT return " Draw " NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT A = [ 4 , 12 , 24 ] NEW_LINE N = len ( A ) NEW_LINE B = [ 25 , 28 , 13 , 45 ] NEW_LINE M = len ( B ) NEW_LINE print ( findwinner ( A , B , N , M ) ) NEW_LINE DEDENT