Find the winner of the game based on greater number of divisors
Given two arrays arr1[] and arr2[], player A picks an element from arr1[] and player B picks an element from arr2[], the player which has the element with more number of divisors wins the round. If both have elements with the same number of divisors then player A wins that round. The task is to find whether player A has more probability of winning the game or player B.
Examples:
Input: arr1[] = {4, 12, 24}, arr2[] = {25, 28, 13, 45}
Output: A
Pairs where A wins are (3, 2), (3, 3), (6, 2), (6, 3), (6, 6), (6, 6), (8, 2), (8, 3), (8, 6) and (8, 6).
Total = 10.
B wins in 2 cases.
Hence, A has more probability of winning the game.Input: arr1[] = {7, 3, 4}, arr2[] = {5, 4, 12, 10}
Output: B
Approach:
- For both the arrays, in place of elements, store the number of divisors of elements.
- Sort both the arrays in increasing order.
- Find all the possible pair selection (X, Y) in which A wins the game.
- Suppose, A chooses an element from arr1[]. Now binary search can be used to find the number of elements in arr2[] which has the divisor count less than the chosen element in arr1[]. This will be added to the count of pairs where A wins. Do this for every element of arr1[].
- N * M is the total pairs possible. The number of pairs where A wins is said X and the number of pairs where B wins is said Y.
- If X > Y then A has more probability of winning the game.
- If Y > X then B has more probability of winning.
- If X = Y then the probability of draw is more.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define ll long long int // Function to return the count // of divisors of elem 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; } // Function to return the winner of the game string findwinner( int A[], int B[], int N, int M) { // Convert every element of A[] // to their divisor count for ( int i = 0; i < N; i++) { A[i] = divisorcount(A[i]); } // Convert every element of B[] // to their divisor count for ( int i = 0; i < M; i++) { B[i] = divisorcount(B[i]); } // Sort both the arrays 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; // For every element of A apply Binary Search // to find number of pairs where A wins while (start <= end) { int mid = (start + end) / 2; if (B[mid] <= val) { index = mid; start = mid + 1; } else { end = mid - 1; } } winA += (index + 1); } // B wins if A doesnot win int winB = N * M - winA; if (winA > winB) { return "A" ; } else if (winB > winA) { return "B" ; } return "Draw" ; } // Driver code 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; } |
Java
// Java implementation of the // above approach import java.util.*; class GFG{ // Function to return the count // of divisors of elem static int divisorcount( int elem) { int ans = 0 ; for ( int i = 1 ; i <= Math.sqrt(elem); i++) { if (elem % i == 0 ) { if (i * i == elem) ans++; else ans += 2 ; } } return ans; } // Function to return the // winner of the game static String findwinner( int A[], int B[], int N, int M) { // Convert every element of A[] // to their divisor count for ( int i = 0 ; i < N; i++) { A[i] = divisorcount(A[i]); } // Convert every element of B[] // to their divisor count for ( int i = 0 ; i < M; i++) { B[i] = divisorcount(B[i]); } // Sort both the arrays Arrays.sort(A); Arrays.sort(B); int winA = 0 ; for ( int i = 0 ; i < N; i++) { int val = A[i]; int start = 0 ; int end = M - 1 ; int index = - 1 ; // For every element of A // apply Binary Search to // find number of pairs // where A wins while (start <= end) { int mid = (start + end) / 2 ; if (B[mid] <= val) { index = mid; start = mid + 1 ; } else { end = mid - 1 ; } } winA += (index + 1 ); } // B wins if A doesnot // win int winB = N * M - winA; if (winA > winB) { return "A" ; } else if (winB > winA) { return "B" ; } return "Draw" ; } // Driver code public static void main(String[] args) { int A[] = { 4 , 12 , 24 }; int N = A.length; int B[] = { 25 , 28 , 13 , 45 }; int M = B.length; System.out.print(findwinner(A, B, N, M)); } } // This code is contributed by Chitranayal |
Python3
# Python3 implementation of the approach from math import * # Function to return the count # of divisors of elem def divisorcount(elem): ans = 0 for i in range ( 1 , int (sqrt(elem)) + 1 ): if (elem % i = = 0 ): if (i * i = = elem): ans + = 1 else : ans + = 2 return ans # Function to return the winner of the game def findwinner(A, B, N, M): # Convert every element of A[] # to their divisor count for i in range (N): A[i] = divisorcount(A[i]) # Convert every element of B[] # to their divisor count for i in range (M): B[i] = divisorcount(B[i]) # Sort both the arrays A.sort() B.sort() winA = 0 for i in range (N): val = A[i] start = 0 end = M - 1 index = - 1 # For every element of A[] apply # binary search to find number # of pairs where A wins while (start < = end): mid = (start + end) / / 2 if (B[mid] < = val): index = mid start = mid + 1 else : end = mid - 1 winA + = (index + 1 ) # B wins if A doesnot win winB = N * M - winA if (winA > winB): return "A" elif (winB > winA): return "B" return "Draw" # Driver code if __name__ = = '__main__' : A = [ 4 , 12 , 24 ] N = len (A) B = [ 25 , 28 , 13 , 45 ] M = len (B) print (findwinner(A, B, N, M)) # This code is contributed by himanshu77 |
C#
// C# implementation of the approach using System; class GFG{ // Function to return the count // of divisors of elem static int divisorcount( int elem) { int ans = 0; for ( int i = 1; i <= Math.Sqrt(elem); i++) { if (elem % i == 0) { if (i * i == elem) ans++; else ans += 2; } } return ans; } // Function to return the // winner of the game static string findwinner( int [] A, int [] B, int N, int M) { // Convert every element of A[] // to their divisor count for ( int i = 0; i < N; i++) { A[i] = divisorcount(A[i]); } // Convert every element of B[] // to their divisor count for ( int i = 0; i < M; i++) { B[i] = divisorcount(B[i]); } // Sort both the arrays Array.Sort(A); Array.Sort(B); int winA = 0; for ( int i = 0; i < N; i++) { int val = A[i]; int start = 0; int end = M - 1; int index = -1; // For every element of A // apply Binary Search to // find number of pairs // where A wins while (start <= end) { int mid = (start + end) / 2; if (B[mid] <= val) { index = mid; start = mid + 1; } else { end = mid - 1; } } winA += (index + 1); } // B wins if A doesnot // win int winB = N * M - winA; if (winA > winB) { return "A" ; } else if (winB > winA) { return "B" ; } return "Draw" ; } // Driver code public static void Main() { int [] A = { 4, 12, 24 }; int N = A.Length; int [] B = { 25, 28, 13, 45 }; int M = B.Length; Console.Write(findwinner(A, B, N, M)); } } // This code is contributed by rishavmahato348 |
Javascript
<script> // JavaScript implementation of the // above approach // Function to return the count // of divisors of elem function divisorcount(elem) { let ans = 0; for (let i = 1; i <= Math.sqrt(elem); i++) { if (elem % i == 0) { if (i * i == elem) ans++; else ans += 2; } } return ans; } // Function to return the // winner of the game function findwinner(A,B,N,M) { // Convert every element of A[] // to their divisor count for (let i = 0; i < N; i++) { A[i] = divisorcount(A[i]); } // Convert every element of B[] // to their divisor count for (let i = 0; i < M; i++) { B[i] = divisorcount(B[i]); } // Sort both the arrays A.sort( function (a,b){ return a-b;}); B.sort( function (a,b){ return a-b;}); let winA = 0; for (let i = 0; i < N; i++) { let val = A[i]; let start = 0; let end = M - 1; let index = -1; // For every element of A // apply Binary Search to // find number of pairs // where A wins while (start <= end) { let mid = Math.floor((start + end) / 2); if (B[mid] <= val) { index = mid; start = mid + 1; } else { end = mid - 1; } } winA += (index + 1); } // B wins if A doesnot // win let winB = N * M - winA; if (winA > winB) { return "A" ; } else if (winB > winA) { return "B" ; } return "Draw" ; } // Driver code let A=[4, 12, 24]; let N = A.length; let B=[25, 28, 13, 45]; let M = B.length; document.write(findwinner(A, B, N, M)); // This code is contributed by rag2127 </script> |
A
Time Complexity: O(n*log(n)+m*log(m)+n*log(m)+n*?a+m*?b) where n and m are size of array and a and b are maximum elements in both arrays respectively.
Auxiliary Space: O(1)