HiveBrain v1.2.0
Get Started
← Back to all entries
snippetModerate

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$?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
suchthehowelementscardinalityarraygreaterthanequalevery

Problem

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:

  • If $T$=[1, 3, 4, 1, 3, 6], then $S$ can be [3, 3, 6] or [3, 4, 6] or [4, 3, 6].



  • 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.)

Solution

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]].

Context

StackExchange Computer Science Q#66048, answer score: 14

Revisions (0)

No revisions yet.