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].
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the minimum removals from // arr such that max(arr) <= 2 * min(arr)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;}// Driver Program to test above functionint main(){ int arr[] = { 4, 5, 3, 8, 3 }; int n = sizeof(arr) / sizeof(arr[0]); cout << minimumRemovals(n, arr); return 0;} |
Java
// Java implementation of the approachimport java.util.*;public class Main { // Function to return the minimum removals from // arr such that max(arr) <= 2 * min(arr) public static int minimumRemovals(int n, int[] a) { // Count occurrence of each element Map<Integer, Integer> ct = new HashMap<>(); for (int i = 0; i < n; i++) { ct.put(a[i], ct.getOrDefault(a[i], 0) + 1); } // Take prefix sum int sm = 0; for (int mn : ct.keySet()) { sm += ct.get(mn); ct.put(mn, sm); } int mx = 0, prev = 0; for (int mn : ct.keySet()) { // Chosen minimum int x = mn; int y = 2 * x; List<Integer> keysList = new ArrayList<>(ct.keySet()); int index = Collections.binarySearch(keysList, y); int pos = index >= 0 ? index : -(index + 1) - 1; Integer itr = pos >= 0 ? ct.get(keysList.get(pos)) : null; // Number of elements that are in // range [x, 2x] int cr = (itr != null ? itr : 0) - prev; mx = Math.max(mx, cr); prev = ct.get(mn); } // Minimum elements to be removed return n - mx; } // Driver Program to test above function public static void main(String[] args) { int[] arr = { 4, 5, 3, 8, 3 }; int n = arr.length; System.out.println(minimumRemovals(n, arr)); }}// This code is contributed by codebraxnzt |
Python3
# Python3 implementation of the approachfrom bisect import bisect_left as upper_bound# Function to return the minimum removals from# arr such that max(arr) <= 2 * min(arr)def minimumRemovals(n, a): # Count occurrence of each element ct = dict() for i in a: ct[i] = ct.get(i, 0) + 1 # Take prefix sum sm = 0 for mn in ct: sm += ct[mn] ct[mn] = sm mx = 0 prev = 0; for mn in ct: # Chosen minimum x = mn y = 2 * x itr = upper_bound(list(ct), y) # Number of elements that are in # range [x, 2x] cr = ct[itr] - prev mx = max(mx, cr) prev = ct[mn] # Minimum elements to be removed return n - mx# Driver Codearr = [4, 5, 3, 8, 3]n = len(arr)print(minimumRemovals(n, arr))# This code is contributed by Mohit Kumar |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class MainClass{ // Function to return the minimum removals from // arr such that max(arr) <= 2 * min(arr) public static int minimumRemovals(int n, int[] a) { // Count occurrence of each element Dictionary<int, int> ct = new Dictionary<int, int>(); for (int i = 0; i < n; i++) { if (ct.ContainsKey(a[i])) { ct[a[i]]++; } else { ct[a[i]] = 1; } } // Take prefix sum int sm = 0; List<int> keysList = new List<int>(ct.Keys); keysList.Sort(); foreach (int mn in keysList) { sm += ct[mn]; ct[mn] = sm; } int mx = 0, prev = 0; foreach (int mn in keysList) { // Chosen minimum int x = mn; int y = 2 * x; int index = keysList.BinarySearch(y); int pos = index >= 0 ? index : -(index + 1) - 1; int itr = pos >= 0 ? ct[keysList[pos]] : 0; // Number of elements that are in // range [x, 2x] int cr = itr - prev; mx = Math.Max(mx, cr); prev = ct[mn]; } // Minimum elements to be removed return n - mx; } // Driver Program to test above function public static void Main() { int[] arr = { 4, 5, 3, 8, 3 }; int n = arr.Length; Console.WriteLine(minimumRemovals(n, arr)); }}// This code is contributed by Prince Kumar |
Javascript
// JavaScript implementation of the approach// Function to return the minimum removals from arr such that max(arr) <= 2 * min(arr)function minimumRemovals(n, a){ // Import upper_bound from bisect const upper_bound = (arr, x) => { let low = 0, high = arr.length; while (low < high) { const mid = (low + high) >>> 1; if (x >= arr[mid]) { low = mid + 1; } else { high = mid; } } return low; } // Count occurrence of each element let ct = new Map(); for (let i of a){ ct.set(i, (ct.get(i) || 0) + 1); } // Take prefix sum let sm = 0; for (let mn of ct.keys()){ sm += ct.get(mn); ct.set(mn, sm); } let mx = 0; let prev = 0; for (let mn of ct.keys()){ // Chosen minimum let x = mn; let y = 2 * x; let itr = upper_bound(Array.from(ct.keys()), y); // Number of elements that are in range [x, 2x] let cr = ct.get([...ct.keys()][itr-1]) - ct.get(mn) + prev; mx = Math.max(mx, cr); prev = ct.get(mn) - (ct.get(mn - 1) || 0); } // Minimum elements to be removed return n - mx;}// Driver Codelet arr = [4, 5, 3, 8, 3];let n = arr.length;console.log(minimumRemovals(n, arr));// This code is contributed by princekumaras |
Output
1
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
