[Solved]: How to find the maximal set of elements $S$ of an array such that every element in $S$ is greater than or equal to the cardinality of $S$?

Problem Detail: 

I have an algorithmic problem.

Given an array (or a set) $T$ of $n$ nonnegative integers. Find the maximal set $S$ of $T$ such that for all $a\in S$, $a\geqslant |S|$.

For example:

1. If $T$=[1, 3, 4, 1, 3, 6], then $S$ can be [3, 3, 6] or [3, 4, 6] or [4, 3, 6].
2. In $T$=[7, 5, 1, 1, 7, 4], then $S$ is [7, 5, 7, 4].

I have tried this recursive function.

function(T):     if minimum(T) >= length(T):          return T     else:          return function(T\minimum(T)) 

Is there any non-recursive algorithm. (I did not check my recursive algorithm, so it could has some flaw.)

Asked By : Azzo

Answered By : Karolis Juodelė

Sort T. Then take elements while T[i] >= i+1.

For example sorted(T)=[6,4,3,3,1,1]. Then, T[0] = 6 > 1, T[1] = 4 > 2, T[2] = 3 <= 3 and finally, T[3] = 3 < 4 so we have S = [T[0], T[1], T[2]].

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/66048