Question

Facebook | Meta | OA | Software Engineer | 2022 | Set-3

Answer 1

Now consider the problem Threshold Largest Smallest (A,T)

 

• INPUT: an unsorted array A of length n, and a positive target integer T. Note that T might be much larger than n. You can assume for this problem that n is even, that all numbers in A are unique, and that all numbers in A are ipsitive integers.

 

OUTPUT: the smallest numberk S n/2 such that SumLargest Smallest (A, k) 2T. Note in particular that k must satisfy SumLargest Smallest (A, k , 1) <T. If SumLargestSmallest (A,n/2) <T then output "No Solution"

 

For example, if A = [10,6, 15, 3, 12, 7,50, 1, 8) and T=80, then the out put should be k= 3 because SumLargestSmallest (4,2)=1+3+50+15= 68 < 80, while SumLargest Smallest (A, 3)=1+3+6+50+15+12= 86> 80.

 

The Problem Write pseudocode for a recursive algorithm Threshold LargestS mallest (A,T) that runs in time O(n). All you need to write is psuedocode, and the recurrence formula of your algorithm.