Dados dos arreglos arr1[] y arr2[] que consisten en N y M enteros respectivamente, la tarea es encontrar la probabilidad de seleccionar aleatoriamente los dos números de arr1[] y arr2[] respectivamente, tal que el primer elemento seleccionado sea estrictamente menor que el segundo elemento seleccionado.
Ejemplos:
Entrada: arr1[] = {3, 2, 1, 1}, arr2[] = {1, 2, 5, 2}
Salida: 0.5
Explicación: Las
siguientes son las formas de seleccionar los elementos de array de ambas arrays, el primer número es menor que el segundo número:
- Al seleccionar arr1[0], hay 1 forma de seleccionar un elemento en arr2[].
- Al seleccionar arr1[1], hay 1 forma de seleccionar un elemento en arr2[].
- Al seleccionar arr1[2], hay 3 formas de seleccionar un elemento en arr2[].
- Al seleccionar arr1[3], hay 3 formas de seleccionar un elemento en arr2[]
Por lo tanto, hay totales de (3 + 3 + 1 + 1 = 8) formas de seleccionar los elementos de ambas arrays que satisfacen las condiciones. Por lo tanto, la probabilidad es (8/(4*4)) = 0,5.
Entrada: arr1[] = {5, 2, 6, 1}, arr2[] = {1, 6, 10, 1}
Salida: 0,4375
Enfoque ingenuo: el problema dado se puede resolver en función de las siguientes observaciones:
- La idea es utilizar el concepto de probabilidad condicional. La probabilidad de seleccionar un elemento de la array arr1[] es 1/N.
- Ahora supongamos que X es el recuento de elementos en arr2[] mayor que los elementos seleccionados de arr1[], entonces la probabilidad de seleccionar uno de esos elementos de arr2[] es X/M .
- Por lo tanto, la probabilidad de seleccionar dos elementos de modo que el primer elemento sea menor que el segundo elemento seleccionado es la suma de (1/N)*(X/M) para cada elemento en arr1[] .
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos, res como 0 para almacenar la probabilidad resultante.
- Recorra la array dada arr1[] y realice los siguientes pasos:
- Encuentre el conteo de elementos en arr2[] mayor que arr1[i] recorriendo el arreglo arr2[] y luego incremente res por él.
- Actualice el valor de res como res = res/N*M .
- Después de completar los pasos anteriores, imprima el valor de res como la probabilidad resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find probability
// such that x < y and X belongs to
// arr1[] and Y belongs to arr2[]
double probability(vector<int> arr1,vector<int> arr2)
{
// Stores the length of arr1
int N = arr1.size();
// Stores the length of arr2
int M = arr2.size();
// Stores the result
double res = 0;
// Traverse the arr1[]
for (int i = 0; i < N; i++) {
// Stores the count of
// elements in arr2 that
// are greater than arr[i]
int y = 0;
// Traverse the arr2[]
for (int j = 0; j < M; j++) {
// If arr2[j] is greater
// than arr1[i]
if (arr2[j] > arr1[i])
y++;
}
// Increment res by y
res += y;
}
// Update the value of res
res = (double)res / (double)(N * M);
// Return resultant probability
return res;
}
// Driver Code
int main()
{
vector<int> arr1 = { 5, 2, 6, 1 };
vector<int> arr2 = { 1, 6, 10, 1 };
cout<<probability(arr1, arr2);
}
// This code is contributed by mohit kumar 29.
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find probability
// such that x < y and X belongs to
// arr1[] and Y belongs to arr2[]
static double probability(int[] arr1,
int[] arr2)
{
// Stores the length of arr1
int N = arr1.length;
// Stores the length of arr2
int M = arr2.length;
// Stores the result
double res = 0;
// Traverse the arr1[]
for (int i = 0; i < N; i++) {
// Stores the count of
// elements in arr2 that
// are greater than arr[i]
int y = 0;
// Traverse the arr2[]
for (int j = 0; j < M; j++) {
// If arr2[j] is greater
// than arr1[i]
if (arr2[j] > arr1[i])
y++;
}
// Increment res by y
res += y;
}
// Update the value of res
res = (double)res / (double)(N * M);
// Return resultant probability
return res;
}
// Driver Code
public static void main(String[] args)
{
int[] arr1 = { 5, 2, 6, 1 };
int[] arr2 = { 1, 6, 10, 1 };
System.out.println(
probability(arr1, arr2));
}
}
Python3
# Python 3 program for the above approach # Function to find probability # such that x < y and X belongs to # arr1[] and Y belongs to arr2[] def probability(arr1, arr2): # Stores the length of arr1 N = len(arr1) # Stores the length of arr2 M = len(arr2) # Stores the result res = 0 # Traverse the arr1[] for i in range(N): # Stores the count of # elements in arr2 that # are greater than arr[i] y = 0 # Traverse the arr2[] for j in range(M): # If arr2[j] is greater # than arr1[i] if (arr2[j] > arr1[i]): y += 1 # Increment res by y res += y # Update the value of res res = res / (N * M) # Return resultant probability return res # Driver Code if __name__ == "__main__": arr1 = [5, 2, 6, 1] arr2 = [1, 6, 10, 1] print(probability(arr1, arr2)) # This code is contributed by ukasp.
C#
//C# program for the above approach
using System;
class GFG {
// Function to find probability
// such that x < y and X belongs to
// arr1[] and Y belongs to arr2[]
static double probability(int[] arr1, int[] arr2)
{
// Stores the length of arr1
int N = arr1.Length;
// Stores the length of arr2
int M = arr2.Length;
// Stores the result
double res = 0;
// Traverse the arr1[]
for (int i = 0; i < N; i++) {
// Stores the count of
// elements in arr2 that
// are greater than arr[i]
int y = 0;
// Traverse the arr2[]
for (int j = 0; j < M; j++) {
// If arr2[j] is greater
// than arr1[i]
if (arr2[j] > arr1[i])
y++;
}
// Increment res by y
res += y;
}
// Update the value of res
res = (double)res / (double)(N * M);
// Return resultant probability
return res;
}
// Driver Code
static void Main()
{
int[] arr1 = { 5, 2, 6, 1 };
int[] arr2 = { 1, 6, 10, 1 };
Console.WriteLine(probability(arr1, arr2));
}
}
// This code is contributed by SoumikMondal.
Javascript
<script>
// Javascript program for the above approach
// Function to find probability
// such that x < y and X belongs to
// arr1[] and Y belongs to arr2[]
function probability(arr1, arr2)
{
// Stores the length of arr1
let N = arr1.length;
// Stores the length of arr2
let M = arr2.length;
// Stores the result
let res = 0;
// Traverse the arr1[]
for (let i = 0; i < N; i++) {
// Stores the count of
// elements in arr2 that
// are greater than arr[i]
let y = 0;
// Traverse the arr2[]
for (let j = 0; j < M; j++) {
// If arr2[j] is greater
// than arr1[i]
if (arr2[j] > arr1[i])
y++;
}
// Increment res by y
res += y;
}
// Update the value of res
res = (res / (N * M));
// Return resultant probability
return res;
}
// Driver Code
let arr1 = [ 5, 2, 6, 1 ];
let arr2 = [ 1, 6, 10, 1 ];
document.write(
probability(arr1, arr2));
</script>
Producción:
0.4375
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de la búsqueda binaria . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos res como 0 que almacena la probabilidad resultante.
- Ordena las arrays en orden ascendente.
- Recorra la array dada arr1[] y realice los siguientes pasos:
- Encuentre el conteo de elementos en arr2[] mayor que arr1[i] usando la búsqueda binaria y luego incremente res por eso.
- Actualice el valor de res como res = res/N*M.
- Después de completar los pasos anteriores, imprima el res como la probabilidad resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
int countGreater(int* arr, int k);
// Function to find probability
// such that x < y and X belongs
// to arr1[] & Y belongs to arr2[]
float probability(int* arr1,
int* arr2)
{
// Stores the length of arr1
int N = 4;
// Stores the length of arr2
int M = 4;
// Stores the result
float res = 0;
// Sort the arr2[] in the
// ascending order
sort(arr2, arr2 + M);
// Traverse the arr1[]
for (int i = 0; i < N; i++) {
// Stores the count of
// elements in arr2 that
// are greater than arr[i]
int y = countGreater(
arr2, arr1[i]);
// Increment res by y
res += y;
}
// Update the resultant
// probability
res = res / (N * M);
// Return the result
return res;
}
// Function to return the count
// of elements from the array
// which are greater than k
int countGreater(int* arr,
int k)
{
int n = 4;
int l = 0;
int r = n - 1;
// Stores the index of the
// leftmost element from the
// array which is at least k
int leftGreater = n;
// Finds number of elements
// greater than k
while (l <= r) {
int m = l + (r - l) / 2;
// If mid element is at least
// K, then update the value
// of leftGreater and r
if (arr[m] > k) {
// Update leftGreater
leftGreater = m;
// Update r
r = m - 1;
}
// If mid element is
// at most K, then
// update the value of l
else
l = m + 1;
}
// Return the count of
// elements greater than k
return (n - leftGreater);
}
// Driver Code
int main()
{
int arr1[] = { 5, 2, 6, 1 };
int arr2[] = { 1, 6, 10, 1 };
cout << probability(arr1, arr2);
return 0;
}
// This code is contributed by Shubhamsingh10
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find probability
// such that x < y and X belongs
// to arr1[] & Y belongs to arr2[]
static double probability(int[] arr1,
int[] arr2)
{
// Stores the length of arr1
int N = arr1.length;
// Stores the length of arr2
int M = arr2.length;
// Stores the result
double res = 0;
// Sort the arr2[] in the
// ascending order
Arrays.sort(arr2);
// Traverse the arr1[]
for (int i = 0; i < N; i++) {
// Stores the count of
// elements in arr2 that
// are greater than arr[i]
int y = countGreater(
arr2, arr1[i]);
// Increment res by y
res += y;
}
// Update the resultant
// probability
res = (double)res / (double)(N * M);
// Return the result
return res;
}
// Function to return the count
// of elements from the array
// which are greater than k
static int countGreater(int[] arr,
int k)
{
int n = arr.length;
int l = 0;
int r = n - 1;
// Stores the index of the
// leftmost element from the
// array which is at least k
int leftGreater = n;
// Finds number of elements
// greater than k
while (l <= r) {
int m = l + (r - l) / 2;
// If mid element is at least
// K, then update the value
// of leftGreater and r
if (arr[m] > k) {
// Update leftGreater
leftGreater = m;
// Update r
r = m - 1;
}
// If mid element is
// at most K, then
// update the value of l
else
l = m + 1;
}
// Return the count of
// elements greater than k
return (n - leftGreater);
}
// Driver Code
public static void main(String[] args)
{
int[] arr1 = { 5, 2, 6, 1 };
int[] arr2 = { 1, 6, 10, 1 };
System.out.println(
probability(arr1, arr2));
}
}
Python3
# Python3 program for the above approach # Function to find probability # such that x < y and X belongs # to arr1[] & Y belongs to arr2[] def probability(arr1, arr2): # Stores the length of arr1 n = len(arr1) # Stores the length of arr2 m = len(arr2) # Stores the result res = 0 # Sort the arr2[] in the # ascending order arr2.sort() # Traverse the arr1[] for i in range(n): # Stores the count of # elements in arr2 that # are greater than arr[i] y = countGreater(arr2, arr1[i]) # Increment res by y res += y # Update the resultant # probability res /= (n * m) # Return the result return res # Function to return the count # of elements from the array # which are greater than k def countGreater(arr, k): n = len(arr) l = 0 r = n - 1 # Stores the index of the # leftmost element from the # array which is at least k leftGreater = n # Finds number of elements # greater than k while l <= r: m = (l + r) // 2 # If mid element is at least # K, then update the value # of leftGreater and r if (arr[m] > k): # Update leftGreater leftGreater = m # Update r r = m - 1 # If mid element is # at most K, then # update the value of l else: l = m + 1 # Return the count of # elements greater than k return n - leftGreater # Driver code if __name__ == '__main__': arr1 = [ 5, 2, 6, 1 ] arr2 = [ 1, 6, 10, 1 ] print(probability(arr1, arr2)) # This code is contributed by MuskanKalra1
C#
// C# program for the above approach
using System;
class GFG {
// Function to find probability
// such that x < y and X belongs
// to arr1[] & Y belongs to arr2[]
static double probability(int[] arr1,
int[] arr2)
{
// Stores the length of arr1
int N = arr1.Length;
// Stores the length of arr2
int M = arr2.Length;
// Stores the result
double res = 0;
// Sort the arr2[] in the
// ascending order
Array.Sort(arr2);
// Traverse the arr1[]
for (int i = 0; i < N; i++) {
// Stores the count of
// elements in arr2 that
// are greater than arr[i]
int y = countGreater(
arr2, arr1[i]);
// Increment res by y
res += y;
}
// Update the resultant
// probability
res = (double)res / (double)(N * M);
// Return the result
return res;
}
// Function to return the count
// of elements from the array
// which are greater than k
static int countGreater(int[] arr,
int k)
{
int n = arr.Length;
int l = 0;
int r = n - 1;
// Stores the index of the
// leftmost element from the
// array which is at least k
int leftGreater = n;
// Finds number of elements
// greater than k
while (l <= r) {
int m = l + (r - l) / 2;
// If mid element is at least
// K, then update the value
// of leftGreater and r
if (arr[m] > k) {
// Update leftGreater
leftGreater = m;
// Update r
r = m - 1;
}
// If mid element is
// at most K, then
// update the value of l
else
l = m + 1;
}
// Return the count of
// elements greater than k
return (n - leftGreater);
}
// Driver code
public static void Main()
{
int[] arr1 = { 5, 2, 6, 1 };
int[] arr2 = { 1, 6, 10, 1 };
Console.Write(
probability(arr1, arr2));
}
}
// This code is contributed by sanjoy_62.
Javascript
<script>
// Javascript program for the above approach
// Function to find probability
// such that x < y and X belongs
// to arr1[] & Y belongs to arr2[]
function probability(arr1, arr2)
{
// Stores the length of arr1
var N = 4;
// Stores the length of arr2
var M = 4;
// Stores the result
var res = 0;
// Sort the arr2[] in the
// ascending order
arr2.sort(function(a, b) {
return a - b;
});
// Traverse the arr1[]
for (var i = 0; i < N; i++) {
// Stores the count of
// elements in arr2 that
// are greater than arr[i]
var y = countGreater( arr2, arr1[i]);
// Increment res by y
res += y;
}
// Update the resultant
// probability
res = res / (N * M);
// Return the result
return res;
}
// Function to return the count
// of elements from the array
// which are greater than k
function countGreater(arr, k)
{
var n = 4;
var l = 0;
var r = n - 1;
// Stores the index of the
// leftmost element from the
// array which is at least k
var leftGreater = n;
// Finds number of elements
// greater than k
while (l <= r) {
var m = Math.floor(l + (r - l) / 2);
// If mid element is at least
// K, then update the value
// of leftGreater and r
if (arr[m] > k) {
// Update leftGreater
leftGreater = m;
// Update r
r = m - 1;
}
// If mid element is
// at most K, then
// update the value of l
else
l = m + 1;
}
// Return the count of
// elements greater than k
return n - leftGreater;
}
// Driver Code
var arr1 = [ 5, 2, 6, 1 ];
var arr2 = [ 1, 6, 10, 1 ];
document.write(probability(arr1, arr2));
// This code is contributed by Shubhamsingh10
</script>
Producción:
0.4375
Complejidad de tiempo: O(N * log M)
Espacio auxiliar: O(1)