Probability that a random pair chosen from an array (a[i], a[j]) has the maximum sum

0 0 5 minutes read

Given an array arr[] of N integers, the task is to find the probability of getting the maximum sum pair (arr[i], arr[j]) from the array when a random pair is chosen.
Examples:

Input: arr[] = {3, 3, 3, 3}
Output: 1
All the pairs will give the maximum sum i.e. 6.
Input: arr[] = {1, 1, 1, 2, 2, 2}
Output: 0.2
Only the pairs (2, 2), (2, 2) and (2, 2) will give
the maximum sum out of 15 pairs.
3 / 15 = 0.2

Approach: Run two nested loops to get the sum for every single pair, keep the maximum sum for any pair and its count (i.e. the number of pairs that give this sum). Now, the probability of getting this sum will be (count / totalPairs) where totalPairs = (n * (n – 1)) / 2.
Below is the implementation of the above approach:

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>

Output:

0.2

Time Complexity: O(N²)

Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!