Dada una array de enteros no negativos. Nuestra tarea es encontrar el número mínimo de elementos tal que su suma sea mayor que la suma del resto de los elementos de la array.
Ejemplos:
Input : arr[] = {3, 1, 7, 1}
Output : 1
Smallest subset is {7}. Sum of
this subset is greater than all
other elements {3, 1, 1}
Input : arr[] = {2, 1, 2}
Output : 2
In this example one element is not
enough. We can pick elements with
values 1, 2 or 2, 2. In any case,
the minimum count is 2.
El enfoque de fuerza bruta es encontrar la suma de todos los subconjuntos posibles y luego comparar la suma con la suma de los elementos restantes.
El Enfoque Eficiente es tomar los elementos más grandes. Ordenamos los valores en orden descendente, luego tomamos elementos del más grande, hasta que obtenemos estrictamente más de la mitad de la suma total de la array dada.
C++
// CPP program to find minimum number of
// elements such that their sum is greater
// than sum of remaining elements of the array.
#include <bits/stdc++.h>
#include <string.h>
using namespace std;
// function to find minimum elements needed.
int minElements(int arr[], int n)
{
// calculating HALF of array sum
int halfSum = 0;
for (int i = 0; i < n; i++)
halfSum = halfSum + arr[i];
halfSum = halfSum / 2;
// sort the array in descending order.
sort(arr, arr + n, greater<int>());
int res = 0, curr_sum = 0;
for (int i = 0; i < n; i++) {
curr_sum += arr[i];
res++;
// current sum greater than sum
if (curr_sum > halfSum)
return res;
}
return res;
}
// Driver function
int main()
{
int arr[] = {3, 1, 7, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << minElements(arr, n) << endl;
return 0;
}
Java
// Java code to find minimum number of elements
// such that their sum is greater than sum of
// remaining elements of the array.
import java.io.*;
import java.util.*;
class GFG {
// Function to find minimum elements needed
static int minElements(int arr[], int n)
{
// Calculating HALF of array sum
int halfSum = 0;
for (int i = 0; i < n; i++)
halfSum = halfSum + arr[i];
halfSum = halfSum / 2;
// Sort the array in ascending order and
// start traversing array from the ascending
// sort in descending order.
Arrays.sort(arr);
int res = 0, curr_sum = 0;
for (int i = n-1; i >= 0; i--) {
curr_sum += arr[i];
res++;
// Current sum greater than sum
if (curr_sum > halfSum)
return res;
}
return res;
}
// Driver Code
public static void main (String[] args) {
int arr[] = {3, 1, 7, 1};
int n = arr.length;
System.out.println(minElements(arr, n));
}
}
// This code is contributed by Gitanjali
Python3
# Python3 code to find minimum number of # elements such that their sum is greater # than sum of remaining elements of the array. # function to find minimum elements needed. def minElements(arr , n): # calculating HALF of array sum halfSum = 0 for i in range(n): halfSum = halfSum + arr[i] halfSum = int(halfSum / 2) # sort the array in descending order. arr.sort(reverse = True) res = 0 curr_sum = 0 for i in range(n): curr_sum += arr[i] res += 1 # current sum greater than sum if curr_sum > halfSum: return res return res # driver code arr = [3, 1, 7, 1] n = len(arr) print(minElements(arr, n) ) # This code is contributed by "Sharad_Bhardwaj".
C#
// C# code to find minimum number of elements
// such that their sum is greater than sum of
// remaining elements of the array.
using System;
class GFG {
// Function to find minimum elements needed
static int minElements(int []arr, int n)
{
// Calculating HALF of array sum
int halfSum = 0;
for (int i = 0; i < n; i++)
halfSum = halfSum + arr[i];
halfSum = halfSum / 2;
// Sort the array in ascending order and
// start traversing array from the ascending
// sort in descending order.
Array.Sort(arr);
int res = 0, curr_sum = 0;
for (int i = n-1; i >= 0; i--) {
curr_sum += arr[i];
res++;
// Current sum greater than sum
if (curr_sum > halfSum)
return res;
}
return res;
}
// Driver Code
public static void Main ()
{
int []arr = {3, 1, 7, 1};
int n = arr.Length;
Console.WriteLine(minElements(arr, n));
}
}
// This code is contributed by vt_m.
PHP
<?php
// PHP program to find minimum number
// of elements such that their sum is
// greater than sum of remaining
// elements of the array.
// function to find minimum elements needed.
function minElements($arr, $n)
{
// calculating HALF of array sum
$halfSum = 0;
for ($i = 0; $i < $n; $i++)
$halfSum = $halfSum + $arr[$i];
$halfSum = $halfSum / 2;
// sort the array in descending order.
rsort($arr);
$res = 0;
$curr_sum = 0;
for ($i = 0; $i < $n; $i++)
{
$curr_sum += $arr[$i];
$res++;
// current sum greater than sum
if ($curr_sum > $halfSum)
return $res;
}
return $res;
}
// Driver Code
$arr = array(3, 1, 7, 1);
$n = sizeof($arr);
echo minElements($arr, $n);
// This code is contributed by ihritik
?>
Javascript
<script>
// Javascript program to find minimum number of
// elements such that their sum is greater
// than sum of remaining elements of the array.
// function to find minimum elements needed.
function minElements(arr, n)
{
// calculating HALF of array sum
let halfSum = 0;
for (let i = 0; i < n; i++)
halfSum = halfSum + arr[i];
halfSum = parseInt(halfSum / 2, 10);
// sort the array in descending order.
arr.sort(function(a, b){return a - b});
arr.reverse();
let res = 0, curr_sum = 0;
for (let i = 0; i < n; i++) {
curr_sum += arr[i];
res++;
// current sum greater than sum
if (curr_sum > halfSum)
return res;
}
return res;
}
let arr = [3, 1, 7, 1];
let n = arr.length;
document.write(minElements(arr, n));
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
1
Complejidad de tiempo: O (n Log n)
Publicación traducida automáticamente
Artículo escrito por Sagar Shukla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA