Find the winner of the game based on greater number of divisors | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long int NEW_LINE int divisorcount ( int elem ) { int ans = 0 ; for ( int i = 1 ; i <= sqrt ( elem ) ; i ++ ) { if ( elem % i == 0 ) { if ( i * i == elem ) ans ++ ; else ans += 2 ; } } return ans ; } string findwinner ( int A [ ] , int B [ ] , int N , int M ) { for ( int i = 0 ; i < N ; i ++ ) { A [ i ] = divisorcount ( A [ i ] ) ; } for ( int i = 0 ; i < M ; i ++ ) { B [ i ] = divisorcount ( B [ i ] ) ; } sort ( A , A + N ) ; sort ( B , B + M ) ; int winA = 0 ; for ( int i = 0 ; i < N ; i ++ ) { int val = A [ i ] ; int start = 0 ; int end = M - 1 ; int index = -1 ; while ( start <= end ) { int mid = ( start + end ) / 2 ; if ( B [ mid ] <= val ) { index = mid ; start = mid + 1 ; } else { end = mid - 1 ; } } winA += ( index + 1 ) ; } int winB = N * M - winA ; if ( winA > winB ) { return " A " ; } else if ( winB > winA ) { return " B " ; } return " Draw " ; } int main ( ) { int A [ ] = { 4 , 12 , 24 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; int B [ ] = { 25 , 28 , 13 , 45 } ; int M = sizeof ( B ) / sizeof ( B [ 0 ] ) ; cout << findwinner ( A , B , N , M ) ; return 0 ; }