Max possible n

Given an unsorted array of integers, you need to return maximum possible n such that the array consists at least n values greater than or equal to n. Array can contain duplicate values.

Example

Sample input : [1, 2, 3, 4] -- output : 2
Sample input : [900, 2, 901, 3, 1000] -- output: 3

Solution

• For every integer between 1..n count them and store in an array
• Now go from n down to 1 and track cumulative count of the counts for each number, as soon as cumulative count hits n or higher than n then return that number

Code

def max_n(arr)
    return nil unless arr

    n = arr.size
    count = [0] * n
    arr.each do |e|
        if e < n
            count[e] += 1
        end
    end

    i = count.size - 1
    while i >= 0 do
        cummulative_count += count[i]
        if cummulative_count >= n
            return i
        end
    end
end