Data Modelling & AI Data Structure & Algorithm

Probability of obtaining pairs from two arrays such that element from the first array is smaller than that of the second array

23 June 2025

0

Given two arrays arr1[] and arr2[] consisting of N and M integers respectively, the task is to find the probability of randomly selecting the two numbers from arr1[] and arr2[] respectively, such that the first selected element is strictly less than the second selected element.

Examples:

Input: arr1[] = {3, 2, 1, 1}, arr2[] = {1, 2, 5, 2}
Output: 0.5
Explanation:
Following are the ways of selecting the array elements from both the arrays first number is less than the second number:

Selecting arr1[0], there are 1 way of selecting an element in arr2[].

Selecting arr1[1], there are 1 way of selecting an element in arr2[].

Selecting arr1[2], there are 3 way of selecting an element in arr2[].

Selecting arr1[3], there are 3 way of selecting an element in arr2[]

Therefore, there are totals of (3 + 3 + 1 + 1 = 8) ways of selecting the elements from both arrays satisfying the conditions. Hence, the probability is (8/(4*4)) = 0.5.

Input: arr1[] = {5, 2, 6, 1}, arr2[] = {1, 6, 10, 1}
Output: 0.4375

Naive Approach: The given problem can be solved based on the following observations:

The idea is to use the concept of conditional probability. The probability of selecting an element from array arr1[] is 1/N.
Now suppose X is the count of elements in arr2[] greater than the selected elements of arr1[] then the probability of selecting one such element from arr2[] is X/M.
Therefore, the probability of selecting two elements such that the first element is less than the second selected element is the sum of (1/N)*(X/M) for every element in arr1[].

Follow the steps below to solve the problem:

Initialize a variable say, res as 0 to stores the resultant probability.
Traverse the given the array arr1[] and perform the following steps:
- Find the count of elements in arr2[] greater than arr1[i] by traversing the array arr2[] and then increment res by it.
- Update the value of res as res = res/N*M.
After completing the above steps, print the value of res as the resultant probability.

Below is the implementation of the above approach:

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>

Output:

0.4375

Time Complexity: O(N * M)
Auxiliary Space: O(1)

Efficient Approach: The above approach can be optimized by using Binary Search. Follow the steps below to solve the problem:

Initialize a variable, say res as 0 that stores the resultant probability.
Sort the arrays in ascending order.
Traverse the given the array arr1[] and perform the following steps:
- Find the count of elements in arr2[] greater than arr1[i] by using binary search and then increment res by it.
- Update the value of res as res = res/N*M.
After completing the above steps, print the res as the resultant probability.

Below is the implementation of the above approach:

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>

Output:

0.4375

Time Complexity: O(N * log M)
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 neveropen!

Probability of obtaining pairs from two arrays such that element from the first array is smaller than that of the second array

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

LangExtract + Milvus: A Practical Guide to Building a Hybrid Document Processing and Search System

Stop Your AI Assistant from Writing Outdated Code with Milvus SDK Code Helper

A Practical Guide for Choosing the Right Vector Database for Your AI Applications

LEAVE A REPLY Cancel reply

Most Popular

TCL debuts the first smart TVs with Google Gemini

Android 16 QPR2 Beta 1 introduces ‘expanded’ dark theme settings

How to record calls on your Samsung Galaxy phone

How to measure (and understand) your smartphone’s charging speed

EDITOR PICKS

TCL debuts the first smart TVs with Google Gemini

Android 16 QPR2 Beta 1 introduces ‘expanded’ dark theme settings

How to record calls on your Samsung Galaxy phone

POPULAR POSTS

TCL debuts the first smart TVs with Google Gemini

Android 16 QPR2 Beta 1 introduces ‘expanded’ dark theme settings

How to record calls on your Samsung Galaxy phone

POPULAR CATEGORY

ABOUT US

FOLLOW US