Approach

The main idea is to maximize the number of wealthy people.

A person is wealthy if they have at least x burles.

For n remaining people, they can all become wealthy if:

total savings >= n * x

What I did

1. Read all the savings and calculate the total sum.
2. Sort the array in descending order.
3. Check whether the total savings is enough for all current n people.
4. If not, remove the person with the smallest savings.
5. Decrease n and repeat.
6. The first time total >= n * x, that n is the maximum possible number of wealthy people.

Why remove the smallest?

We want to keep as many people as possible.

Therefore, if the current group cannot make everyone wealthy, we remove the person with the smallest amount of savings. This leaves the people with larger savings and gives us the best chance to satisfy the condition for the remaining group.

Complexity

Sorting takes O(n log n).

The loop takes O(n).

Therefore, the overall complexity is:

O(n log n)

C++ Code

#include<iostream>
#include<vector>
#include<al