Test Series Algorithms

Question

Comments

I am not getting the correct answer.

But why can't we just sort the array, say arr, having n elements of set S in O(nlogn) time and then find the values at index K₁,K₂..K_r.

For that we need to go through the K set once. Pick up each element and print arr[K_i]. This would take O(r) as there are r elements in K set.

So O(nlogn) + O(r) = O(nlogn+r)

The highest value of K_i can't be more than the number of elements in n. Because if there are 200 elements(n) is a set, we should not be asked to find the 201^st smallest element. Max range of K_i can be from i=0 to i=n-1. Assuming that K_i does not repeat in the set, no. of  K_i can be maximum 'n' i.e. max(r)=n.

Hence, O(nlogn+r) becomes O(nlogn).

Do you have the solution? Please share if yes.

---

Also thought same thing, don't know how they gave r logn .  there is no explanation given.