Question

Shruti and Manas are playing with numbers. Manas gave N distinct numbers to Shruti. Shruti will insert all these N elements to a set S. Now, Manas asks Shruti to tell Kth greatest element present in the set after performing the following task: 1) Shruti has to choose all pairs of two numbers from the set and find their absolute difference an insert this difference back into the set. 2) Shruti has to perform the above operation on S until |S| no longer changes. Can you help Shruti? Input: 3 2 6 10 2 Output: 8

Answer 1

Answer:

We are given an array of size n containing positive integers. The absolute difference between values at indices i and j is |a[i] – a[j]|. There are n*(n-1)/2 such pairs and we are asked to print the kth (1 <= k <= n*(n-1)/2) the smallest absolute difference among all these pairs.

Explanation:

Input : a[] = {1, 2, 3, 4}

k = 3

Output : 1

The possible absolute differences are :

{1, 2, 3, 1, 2, 1}.

The 3rd smallest value among these is 1.

Input : n = 2

a[] = {10, 10}

k = 1

Output : 0