Suppose an array A of n numbers is given along with an integer M. Assume that an algorithm which finds the median of an unsorted array in linear time is also given. Design a O(n) algorithm that finds the largest subset S = {1, 2, · · · , n} satisfying ∑(i belonging to S) A[i] <= M.
∑ is sum symbol. I can find a algorithm like search to satisfy the time complexity.
Anyone have some simple way to fix it?