Dada una array arr[] de N enteros, la tarea es encontrar la probabilidad de obtener el par de suma máxima (arr[i], arr[j]) de la array cuando se elige un par aleatorio.
Ejemplos:
Entrada: arr[] = {3, 3, 3, 3}
Salida: 1
Todos los pares darán la suma máxima, es decir, 6.
Entrada: arr[] = {1, 1, 1, 2, 2, 2}
Salida: 0.2
Solo los pares (2, 2), (2, 2) y (2, 2) darán
la suma máxima de 15 pares.
3 / 15 = 0,2
Enfoque: ejecute dos bucles anidados para obtener la suma de cada par, mantenga la suma máxima para cualquier par y su cuenta (es decir, la cantidad de pares que dan esta suma). Ahora, la probabilidad de obtener esta suma será (count / totalPairs) donde totalPairs = (n * (n – 1)) / 2 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the probability
// of getting the maximum pair sum
// when a random pair is chosen
// from the given array
float findProb(int arr[], int n)
{
// Initialize the maximum sum, its count
// and the count of total pairs
long maxSum = INT_MIN, maxCount = 0, totalPairs = 0;
// For every single pair
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
// Get the sum of the current pair
int sum = arr[i] + arr[j];
// If the sum is equal to the current
// maximum sum so far
if (sum == maxSum) {
// Increment its count
maxCount++;
}
// If the sum is greater than
// the current maximum
else if (sum > maxSum) {
// Update the current maximum and
// re-initialize the count to 1
maxSum = sum;
maxCount = 1;
}
totalPairs++;
}
}
// Find the required probability
float prob = (float)maxCount / (float)totalPairs;
return prob;
}
// Driver code
int main()
{
int arr[] = { 1, 1, 1, 2, 2, 2 };
int n = sizeof(arr) / sizeof(int);
cout << findProb(arr, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the probability
// of getting the maximum pair sum
// when a random pair is chosen
// from the given array
static float findProb(int arr[], int n)
{
// Initialize the maximum sum, its count
// and the count of total pairs
long maxSum = Integer.MIN_VALUE,
maxCount = 0, totalPairs = 0;
// For every single pair
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
// Get the sum of the current pair
int sum = arr[i] + arr[j];
// If the sum is equal to the current
// maximum sum so far
if (sum == maxSum)
{
// Increment its count
maxCount++;
}
// If the sum is greater than
// the current maximum
else if (sum > maxSum)
{
// Update the current maximum and
// re-initialize the count to 1
maxSum = sum;
maxCount = 1;
}
totalPairs++;
}
}
// Find the required probability
float prob = (float)maxCount /
(float)totalPairs;
return prob;
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 1, 1, 2, 2, 2 };
int n = arr.length;
System.out.println(findProb(arr, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach import sys # Function to return the probability # of getting the maximum pair sum # when a random pair is chosen # from the given array def findProb(arr, n) : # Initialize the maximum sum, its count # and the count of total pairs maxSum = -(sys.maxsize - 1); maxCount = 0; totalPairs = 0; # For every single pair for i in range(n - 1) : for j in range(i + 1, n) : # Get the sum of the current pair sum = arr[i] + arr[j]; # If the sum is equal to the current # maximum sum so far if (sum == maxSum) : # Increment its count maxCount += 1; # If the sum is greater than # the current maximum elif (sum > maxSum) : # Update the current maximum and # re-initialize the count to 1 maxSum = sum; maxCount = 1; totalPairs += 1; # Find the required probability prob = maxCount / totalPairs; return prob; # Driver code if __name__ == "__main__" : arr = [ 1, 1, 1, 2, 2, 2 ]; n = len(arr); print(findProb(arr, n)); # This code is contributed by AnkitRai01
C#
// C# implementation of above approach
using System;
class GFG
{
// Function to return the probability
// of getting the maximum pair sum
// when a random pair is chosen
// from the given array
static float findProb(int []arr, int n)
{
// Initialize the maximum sum, its count
// and the count of total pairs
long maxSum = int.MinValue,
maxCount = 0, totalPairs = 0;
// For every single pair
for (int i = 0; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
// Get the sum of the current pair
int sum = arr[i] + arr[j];
// If the sum is equal to the current
// maximum sum so far
if (sum == maxSum)
{
// Increment its count
maxCount++;
}
// If the sum is greater than
// the current maximum
else if (sum > maxSum)
{
// Update the current maximum and
// re-initialize the count to 1
maxSum = sum;
maxCount = 1;
}
totalPairs++;
}
}
// Find the required probability
float prob = (float)maxCount /
(float)totalPairs;
return prob;
}
// Driver code
public static void Main(String []args)
{
int []arr = { 1, 1, 1, 2, 2, 2 };
int n = arr.Length;
Console.WriteLine(findProb(arr, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Function to return the probability
// of getting the maximum pair sum
// when a random pair is chosen
// from the given array
function findProb(arr, n)
{
// Initialize the maximum sum, its count
// and the count of total pairs
var maxSum = -100000000, maxCount = 0, totalPairs = 0;
// For every single pair
for (var i = 0; i < n - 1; i++) {
for (var j = i + 1; j < n; j++) {
// Get the sum of the current pair
var sum = arr[i] + arr[j];
// If the sum is equal to the current
// maximum sum so far
if (sum == maxSum) {
// Increment its count
maxCount++;
}
// If the sum is greater than
// the current maximum
else if (sum > maxSum) {
// Update the current maximum and
// re-initialize the count to 1
maxSum = sum;
maxCount = 1;
}
totalPairs++;
}
}
// Find the required probability
var prob = maxCount / totalPairs;
return prob;
}
// Driver code
var arr = [ 1, 1, 1, 2, 2, 2 ]
var n = arr.length;
document.write(findProb(arr, n));
// This code is contributed by rutvik_56.
</script>
Producción:
0.2
Complejidad temporal: O(N 2 )
Espacio Auxiliar: O(1)