Dadas dos arrays arr1[] y arr2[] , el jugador A elige un elemento de arr1[] y el jugador B elige un elemento de arr2[] , el jugador que tiene el elemento con más número de divisores gana la ronda. Si ambos tienen elementos con el mismo número de divisores, el jugador A gana esa ronda. La tarea es encontrar si el jugador A tiene más probabilidad de ganar el juego o el jugador B.
Ejemplos:
Entrada: arr1[] = {4, 12, 24}, arr2[] = {25, 28, 13, 45}
Salida: A Los
pares donde A gana son (3, 2), (3, 3), (6, 2), (6, 3), (6, 6), (6, 6), (8, 2), (8, 3), (8, 6) y (8, 6).
Total = 10.
B gana en 2 casos.
Por lo tanto, A tiene más probabilidad de ganar el juego.Entrada: arr1[] = {7, 3, 4}, arr2[] = {5, 4, 12, 10}
Salida: B
Acercarse:
- Para ambas arrays, en lugar de elementos, almacene el número de divisores de elementos.
- Ordene ambas arrays en orden creciente.
- Encuentre todas las posibles selecciones de pares (X, Y) en las que A gana el juego.
- Supongamos que A elige un elemento de arr1[] . Ahora se puede usar la búsqueda binaria para encontrar el número de elementos en arr2[] que tiene el divisor contando menos que el elemento elegido en arr1[] . Esto se sumará al conteo de parejas donde A gane. Haz esto para cada elemento de arr1[] .
- N * M es el total de pares posibles. El número de pares donde gana A se dice X y el número de pares donde gana B se dice Y .
- Si X > Y entonces A tiene más probabilidad de ganar el juego.
- Si Y > X entonces B tiene más probabilidad de ganar.
- Si X = Y entonces la probabilidad de empate es mayor.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
A
Complejidad de tiempo : O(n*log(n)+m*log(m)+n*log(m)+n*√a+m*√b) donde n y m son el tamaño de la array y a y b son máximos elementos en ambas arrays respectivamente.
Espacio Auxiliar : O(1)