Dada una array de tamaño N . La tarea es eliminar los elementos mínimos de la array de modo que el doble del número mínimo sea mayor que el número máximo en la array modificada. Imprime el número mínimo de elementos eliminados.
Ejemplos:
Entrada: arr[] = {4, 5, 100, 9, 10, 11, 12, 15, 200}
Salida: 4
Elimina 4 elementos (4, 5, 100, 200)
para que 2*min sea mayor que max.
Entrada: arr[] = {4, 7, 5, 6}
Salida: 0
Acercarse:
- ordenar la array dada
- Recorra de izquierda a derecha en la array y para cada elemento elegido (que sea x) con el índice i, encuentre el límite superior de (2*x). sea ese índice j. Luego, actualice nuestra respuesta requerida por (n-j+i) si (n-j+i) es menor que el valor actual de nuestra respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to remove minimum elements from the
// array such that 2*min becomes more than max
#include <bits/stdc++.h>
using namespace std;
// Function to remove minimum elements from the
// array such that 2*min becomes more than max
int Removal(vector<int> v, int n)
{
// Sort the array
sort(v.begin(), v.end());
// To store the required answer
int ans = INT_MAX;
// Traverse from left to right
for (vector<int>::iterator i = v.begin(); i != v.end();
i++) {
vector<int>::iterator j = upper_bound(v.begin(),
v.end(), (2 * (*i)));
// Update the answer
ans = min(ans, n - (int)(j - i));
}
// Return the required answer
return ans;
}
// Driver code
int main()
{
vector<int> a = { 4, 5, 100, 9, 10, 11, 12, 15, 200 };
int n = a.size();
// Function call
cout << Removal(a, n);
return 0;
}
Java
// Java program to remove minimum elements from the
// array such that 2*min becomes more than max
import java.util.Arrays;
class GFG
{
// Function to calculate upper bound
public static int upperBound(int[] array,
int value)
{
int low = 0;
int high = array.length;
while (low < high)
{
final int mid = (low + high) / 2;
if (value >= array[mid])
{
low = mid + 1;
}
else
{
high = mid;
}
}
return low;
}
// Function to remove minimum elements from the
// array such that 2*min becomes more than max
public static int Removal(int[] v, int n)
{
// Sort the array
Arrays.sort(v);
// To store the required answer
int ans = Integer.MAX_VALUE;
int k = 0;
// Traverse from left to right
for (int i : v)
{
int j = upperBound(v, (2 * i));
// Update the answer
ans = Math.min(ans, n - (j - k));
k++;
}
// Return the required answer
return ans;
}
// Driver code
public static void main(String[] args)
{
int[] a = { 4, 5, 100, 9, 10,
11, 12, 15, 200 };
int n = a.length;
// Function call
System.out.println(Removal(a, n));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 program to remove minimum elements from the # array such that 2*min becomes more than max from bisect import bisect_left as upper_bound # Function to remove minimum elements from the # array such that 2*min becomes more than max def Removal(v, n): # Sort the array v = sorted(v) # To store the required answer ans = 10**9 # Traverse from left to right for i in range(len(v)): j = upper_bound(v, (2 * (a[i]))) # Update the answer ans = min(ans, n - (j - i - 1)) # Return the required answer return ans # Driver code a = [4, 5, 100, 9, 10, 11, 12, 15, 200] n = len(a) # Function call print(Removal(a, n)) # This code is contributed by Mohit Kumar
C#
// C# program to remove minimum elements
// from the array such that 2*min becomes
// more than max
using System;
class GFG
{
// Function to calculate upper bound
public static int upperBound(int[] array,
int value)
{
int low = 0;
int high = array.Length;
while (low < high)
{
int mid = (low + high) / 2;
if (value >= array[mid])
{
low = mid + 1;
}
else
{
high = mid;
}
}
return low;
}
// Function to remove minimum elements from the
// array such that 2*min becomes more than max
public static int Removal(int[] v, int n)
{
// Sort the array
Array.Sort(v);
// To store the required answer
int ans = int.MaxValue;
int k = 0;
// Traverse from left to right
foreach (int i in v)
{
int j = upperBound(v, (2 * i));
// Update the answer
ans = Math.Min(ans, n - (j - k));
k++;
}
// Return the required answer
return ans;
}
// Driver code
public static void Main(String[] args)
{
int[] a = { 4, 5, 100, 9, 10,
11, 12, 15, 200 };
int n = a.Length;
// Function call
Console.WriteLine(Removal(a, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to remove minimum elements
// from the array such that 2*min becomes
// more than max
// Function to calculate upper bound
function upperBound(array, value) {
var low = 0;
var high = array.length;
while (low < high) {
var mid = parseInt((low + high) / 2);
if (value >= array[mid]) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
// Function to remove minimum elements from the
// array such that 2*min becomes more than max
function Removal(v, n) {
// Sort the array
v.sort((a, b) => a - b);
// To store the required answer
var ans = 2147483648;
var k = 0;
// Traverse from left to right
for (const i of v) {
var j = upperBound(v, 2 * i);
// Update the answer
ans = Math.min(ans, n - (j - k));
k++;
}
// Return the required answer
return ans;
}
// Driver code
var a = [4, 5, 100, 9, 10, 11, 12, 15, 200];
var n = a.length;
// Function call
document.write(Removal(a, n));
</script>
Producción:
4
Complejidad del tiempo: O(NlogN)
Espacio Auxiliar: O(1)