Remove minimum elements from array so that max <= 2 * min

https://www.geeksforgeeks.org/remove-minimum-elements-from-array-so-that-max/

Given an array arr, the task is to remove minimum number of elements such that after their removal, max(arr) <= 2 * min(arr).

Examples:

Input: arr[] = {4, 5, 3, 8, 3}
Output: 1
Remove 8 from the array.

Input: arr[] = {1, 2, 3, 4}
Output: 1
Remove 1 from the array.

Approach: Let us fix each value as the minimum value say x and find number of terms that are in range [x, 2*x]. This can be done using prefix-sums, we can use map (implements self balancing BST) instead of array as the values can be large. The remaining terms which are not in range [x, 2*x] will have to be removed. So, across all values of x, we choose the one which maximises the number of terms in range [x, 2*x].

int minimumRemovals(int n, int a[])

{

    // Count occurrence of each element

    map<int, int> ct;

    for (int i = 0; i < n; i++)

        ct[a[i]]++;

  

    // Take prefix sum

    int sm = 0;

    for (auto mn : ct) {

        sm += mn.second;

        ct[mn.first] = sm;

    }

  

    int mx = 0, prev = 0;

    for (auto mn : ct) {

  

        // Chosen minimum

        int x = mn.first;

        int y = 2 * x;

        auto itr = ct.upper_bound(y);

        itr--;

  

        // Number of elements that are in

        // range [x, 2x]

        int cr = (itr->second) - prev;

        mx = max(mx, cr);

        prev = mn.second;

    }

  

    // Minimum elements to be removed

    return n - mx;

}