Given two arrays A and B, a random pair is picked having an element from array A and another from array B. Output the probability of the pair being maximum weighted.
Input : A[] = 1 2 3
B[] = 1 3 3
Output : 0.222
Explanation : Possible pairs are : {1, 1},
{1, 3}, {1, 3}, {2, 1}, {2, 3}, {2, 3},
{3, 1}, {3, 3}, {3, 3} i.e. 9.
The pair with maximum weight is {3, 3} with
frequency 2. So, the probability of random
pair being maximum is 2/9 = 0.2222.
- Brute Force Method : Generate all possible pairs in N^2 time complexity and count
maximum weighted pairs.
- Better Method : Sort both the arrays and count the last (max) elements from A and B. No. of maximum weighted pairs will be product of both counts. The probability will be
(product of counts) / sizeof(A) * sizeof(B)
- Best Method Best approach will be to traverse both the arrays and count the maximum element. No. of maximum weighted pairs will be product of both counts. The probability will be (product of counts) / sizeof(A) * sizeof(B)
Below is the implementation:
C++
#include <bits/stdc++.h>
using namespace std;
double probability( int a[], int b[], int size1,
int size2)
{
int max1 = INT_MIN, count1 = 0;
for ( int i = 0; i < size1; i++) {
if (a[i] > max1) {
max1 = a[i];
count1 = 1;
}
else if (a[i] == max1) {
count1++;
}
}
int max2 = INT_MIN, count2 = 0;
for ( int i = 0; i < size2; i++) {
if (b[i] > max2) {
max2 = b[i];
count2 = 1;
}
else if (b[i] == max2) {
count2++;
}
}
return ( double )(count1 * count2) /
(size1 * size2);
}
int main()
{
int a[] = { 1, 2, 3 };
int b[] = { 1, 3, 3 };
int size1 = sizeof (a) / sizeof (a[0]);
int size2 = sizeof (b) / sizeof (b[0]);
cout << probability(a, b, size1, size2);
return 0;
}
|
Java
import java.io.*;
class GFG {
static double probability( int a[], int b[],
int size1, int size2)
{
int max1 = Integer.MIN_VALUE, count1 = 0 ;
for ( int i = 0 ; i < size1; i++) {
if (a[i] > max1) {
max1 = a[i];
count1 = 1 ;
}
else if (a[i] == max1) {
count1++;
}
}
int max2 = Integer.MIN_VALUE, count2 = 0 ;
for ( int i = 0 ; i < size2; i++) {
if (b[i] > max2) {
max2 = b[i];
count2 = 1 ;
}
else if (b[i] == max2) {
count2++;
}
}
return ( double )(count1 * count2) / (size1 * size2);
}
public static void main(String args[])
{
int a[] = { 1 , 2 , 3 };
int b[] = { 1 , 3 , 3 };
int size1 = a.length;
int size2 = b.length;
System.out.println(probability(a, b,
size1, size2));
}
}
|
Python3
import sys
def probability(a, b, size1, size2):
max1 = - (sys.maxsize - 1 )
count1 = 0
for i in range (size1):
if a[i] > max1:
count1 = 1
elif a[i] = = max1:
count1 + = 1
max2 = - (sys.maxsize - 1 )
count2 = 0
for i in range (size2):
if b[i] > max2:
max2 = b[i]
count2 = 1
elif b[i] = = max2:
count2 + = 1
return round ((count1 * count2) /
(size1 * size2), 6 )
a = [ 1 , 2 , 3 ]
b = [ 1 , 3 , 3 ]
size1 = len (a)
size2 = len (b)
print (probability(a, b, size1, size2))
|
C#
using System;
class GFG {
static float probability( int []a, int []b,
int size1, int size2)
{
int max1 = int .MinValue, count1 = 0;
for ( int i = 0; i < size1; i++) {
if (a[i] > max1) {
max1 = a[i];
count1 = 1;
}
else if (a[i] == max1) {
count1++;
}
}
int max2 = int .MinValue, count2 = 0;
for ( int i = 0; i < size2; i++) {
if (b[i] > max2) {
max2 = b[i];
count2 = 1;
}
else if (b[i] == max2) {
count2++;
}
}
return ( float )(count1 * count2) /
(size1 * size2);
}
public static void Main()
{
int []a = { 1, 2, 3 };
int []b = { 1, 3, 3 };
int size1 = a.Length;
int size2 = b.Length;
Console.WriteLine(probability(a, b,
size1, size2));
}
}
|
PHP
<?php
function probability( $a , $b ,
$size1 , $size2 )
{
$max1 = PHP_INT_MIN; $count1 = 0;
for ( $i = 0; $i < $size1 ; $i ++)
{
if ( $a [ $i ] > $max1 )
{
$max1 = $a [ $i ];
$count1 = 1;
}
else if ( $a [ $i ] == $max1 )
{
$count1 ++;
}
}
$max2 = PHP_INT_MIN; $count2 = 0;
for ( $i = 0; $i < $size2 ; $i ++)
{
if ( $b [ $i ] > $max2 )
{
$max2 = $b [ $i ];
$count2 = 1;
}
else if ( $b [ $i ] == $max2 )
{
$count2 ++;
}
}
return (double)( $count1 * $count2 ) /
( $size1 * $size2 );
}
$a = array (1, 2, 3);
$b = array (1, 3, 3);
$size1 = sizeof( $a );
$size2 = sizeof( $b );
echo probability( $a , $b ,
$size1 , $size2 );
?>
|
Javascript
<script>
function probability(a, b, size1, size2)
{
let max1 = Number.MIN_VALUE, count1 = 0;
for (let i = 0; i < size1; i++)
{
if (a[i] > max1)
{
max1 = a[i];
count1 = 1;
}
else if (a[i] == max1)
{
count1++;
}
}
let max2 = Number.MIN_VALUE, count2 = 0;
for (let i = 0; i < size2; i++)
{
if (b[i] > max2)
{
max2 = b[i];
count2 = 1;
}
else if (b[i] == max2)
{
count2++;
}
}
return (count1 * count2) /
(size1 * size2);
}
let a = [ 1, 2, 3 ];
let b = [ 1, 3, 3 ];
let size1 = a.length;
let size2 = b.length;
document.write(probability(a, b,
size1, size2));
</script>
|
Time Complexity: O(n).
Auxiliary Space: O(1).