RNDPAIR - Editorial

editorial
, , , , , ,
1

Problem Link

Practice

Contest

Setter: Hasan Jaddouh

Tester: Amr Mahmoud

Editorialist: Bhuvnesh Jain

Difficulty

CAKEWALK

Prerequisites

Probability, Looping techniques

Problem

Find the probability of chosing pair (i, j), i < j such that A[i] + A[j] is maximum.

Explanation

The probability of any event is defined as

P(event) = \frac{\text{number of favourable outcome}}{\text{total number of outcomes}}

The total number of outcomes is \frac{N * (N-1)}{2}, where N = size of array. To calculate the number of favorable outcomes, we can first do a brute force over all pair (i, j), i < j to get the maximum value possible and then again do a brute force to calculate the number of times the maximum is attained.

The complexity of the above approach is O({N}^{2}). This will easily pass the test cases as constraints are low. To solve the problem in O(n), we observe that maximum is obtained when 2 most maximum elements of an array are added. Thus, it boils down to calculating the frequency of them and then finding the number of favorable outcomes in O(1), using the formula:

Favourable outcomes = f2, i.e. frequency of second maximum element, if maximum element occurs only once.

OR

Favourable outcomes = \frac{f1 * (f1-1)}{2}, if maximum element has frequency greater than 1.

Time Complexity

O(N^2), or O(N) per test case.

Space Complexity

O(N)

Solution Links

Setter’s solution

Tester’s solution

Editorialist’s solution

2

@arnavvarshney Here is my approach ::

for _ in xrange(input()):
n = input()
arr = readInts()
arr = rsorted(arr)
count = countchars(arr)
# print count
if arr[0] == arr[1]:
    print (count[arr[0]]*(count[arr[0]]-1))/(n*(n-1.0))
else:
    print (2*count[arr[1]])/(n*(n-1.0))
1 Like