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 Codeint 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 approachimport 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 Codeif __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 approachusing 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 kint 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 Codeint 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 approachimport 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 kdef 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 codeif __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 approachusing 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 kfunction 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 Codevar 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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
