Recuento máximo y mínimo de elementos con suma como máximo K

Dada una array arr[] de tamaño N y un entero K , la tarea es encontrar el número máximo y mínimo de elementos cuya suma sea menor que igual a K.

Ejemplos:

Entrada: N = 4, arr[ ] = {6, 2, 1, 3}, K = 7
Salida: 3 1
Explicación:
Número máximo de elementos cuya suma es menor que K es 3, es decir, [1, 2, 3 ] 
El número mínimo de elementos cuya suma es menor que igual a K es 1, es decir, [6]

Entrada: N = 5, arr[] = {6, 2, 11, 3, 20}, K = 50
Salida: 5 5

Enfoque: este problema se puede resolver ordenando la array arr[]. Siga los pasos a continuación para resolver este problema:

• Ordene la array arr[].
• Inicialice la variable maxNumEle y minNumEle como 0 para almacenar el número mínimo y máximo de elementos cuya suma sea inferior a K .
• Inicialice una variable cumSum1 para almacenar la suma acumulada de la array arr[].
• Iterar en el rango [0, N-1] , usando la variable i:
  • Agrega el elemento actual en cumSum1 .
  • Si cumSum1 es menor que igual a K, entonces incremente en 1 en maxNumEle, de lo contrario rompa el ciclo.
• Inicialice una variable cumSum2 para almacenar la suma acumulativa de la array arr[] .
• Iterar en el rango [N-1, 0], usando la variable i :
  • Agrega el elemento actual en cumSum2 .
  • Si cumSum2 es menor que K , entonces incremente en 1 en minNumEle, de lo contrario rompa el bucle.
• Después de completar los pasos anteriores, imprima maxNumEle y minNumEle como respuesta .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum
// and minimum number of elements
// whose sum is less than equal
// to K
int findMinMax(int arr[], int N, int K)
{
 
    // Sorting both arrays
    sort(arr, arr + N);
 
    // To store the minimum and maximum
    // number of elements whose sum is
    // less than equal to K
    int maxNumEle = 0;
    int minNumEle = 0;
 
    // Store the cumulative sum
    int i, cumSum1 = 0;
 
    // Iterate in the range [0, N-1]
    for (i = 0; i < N; i++) {
        cumSum1 += arr[i];
 
        // If cumSum1 is less than K
        if (cumSum1 <= K)
            maxNumEle += 1;
        else
            break;
    }
    // Store the cumulative sum
    int cumSum2 = 0;
 
    // Iterate in the range [N-1, 0]
    for (i = N - 1; i >= 0; i--) {
 
        cumSum2 += arr[i];
 
        // If cumSum2 is less than K
        if (cumSum2 <= K)
            minNumEle += 1;
        else
            break;
    }
    // Print the value of maxNumEle and minNumEle
    cout << maxNumEle << " " << minNumEle;
}
// Driver Code
 
int main()
{
    // Given Input
    int N = 4;
    int K = 7;
    int arr[] = { 6, 2, 1, 3 };
 
    // Function Call
    findMinMax(arr, N, K);
 
    return 0;
}
// This code is contributed by Potta Lokesh

// Java program for the above approach
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Function to find the maximum
// and minimum number of elements
// whose sum is less than equal
// to K
static void findMinMax(int arr[], int N, int K)
{
     
    // Sorting both arrays
    Arrays.sort(arr);
  
    // To store the minimum and maximum
    // number of elements whose sum is
    // less than equal to K
    int maxNumEle = 0;
    int minNumEle = 0;
  
    // Store the cumulative sum
    int i, cumSum1 = 0;
  
    // Iterate in the range [0, N-1]
    for(i = 0; i < N; i++)
    {
        cumSum1 += arr[i];
  
        // If cumSum1 is less than K
        if (cumSum1 <= K)
            maxNumEle += 1;
        else
            break;
    }
     
    // Store the cumulative sum
    int cumSum2 = 0;
  
    // Iterate in the range [N-1, 0]
    for(i = N - 1; i >= 0; i--)
    {
        cumSum2 += arr[i];
  
        // If cumSum2 is less than K
        if (cumSum2 <= K)
            minNumEle += 1;
        else
            break;
    }
     
    // Print the value of maxNumEle and minNumEle
    System.out.println(maxNumEle + " " + minNumEle);
}
 
// Driver code
public static void main(String[] args)
{
     
    // Given Input
    int N = 4;
    int K = 7;
    int arr[] = { 6, 2, 1, 3 };
  
    // Function Call
    findMinMax(arr, N, K);
}
}
 
// This code is contributed by sanjoy_62

# Python program for the above approach
 
# Function to find the maximum
# and minimum number of elements
# whose sum is less than equal
# to K
def findMinMax(arr, N, K):
   
    # Sorting both arrays
    arr.sort()
 
    # To store the minimum and maximum
    # number of elements whose sum is
    # less than equal to K
    maxNumEle = minNumEle = 0
     
    # Store the cumulative sum
    cumSum1 = 0
 
    # Iterate in the range [0, N-1]
    for i in range(N):
        cumSum1 += arr[i]
         
        # If cumSum1 is less than K
        if cumSum1 <= K:
            maxNumEle += 1
        else:
            break
     
    # Store the cumulative sum
    cumSum2 = 0
 
    # Iterate in the range [N-1, 0]
    for i in range(N-1, 0, -1):
         
        cumSum2 += arr[i]
         
        # If cumSum2 is less than K
        if cumSum2 <= K:
            minNumEle += 1
        else:
            break
 
    # Print the value of maxNumEle and minNumEle
    print(maxNumEle, minNumEle)
     
 
# Driver Code
if __name__ == '__main__':
 
    # Given Input
    N = 4
    K = 7
    arr = [ 6, 2, 1, 3 ]
 
    # Function Call
    findMinMax(arr, N, K)

// C# program for the above approach
using System;
 
class GFG{
     
// Function to find the maximum
// and minimum number of elements
// whose sum is less than equal
// to K
static void findMinMax(int[] arr, int N, int K)
{
     
    // Sorting both arrays
    Array.Sort(arr);
  
    // To store the minimum and maximum
    // number of elements whose sum is
    // less than equal to K
    int maxNumEle = 0;
    int minNumEle = 0;
  
    // Store the cumulative sum
    int i, cumSum1 = 0;
  
    // Iterate in the range [0, N-1]
    for(i = 0; i < N; i++)
    {
        cumSum1 += arr[i];
  
        // If cumSum1 is less than K
        if (cumSum1 <= K)
            maxNumEle += 1;
        else
            break;
    }
     
    // Store the cumulative sum
    int cumSum2 = 0;
  
    // Iterate in the range [N-1, 0]
    for(i = N - 1; i >= 0; i--)
    {
        cumSum2 += arr[i];
  
        // If cumSum2 is less than K
        if (cumSum2 <= K)
            minNumEle += 1;
        else
            break;
    }
     
    // Print the value of maxNumEle and minNumEle
    Console.WriteLine(maxNumEle + " " + minNumEle);
}
 
// Driver code
static public void Main()
{
     
    // Given Input
    int N = 4;
    int K = 7;
    int[] arr = { 6, 2, 1, 3 };
  
    // Function Call
    findMinMax(arr, N, K);
}
}
 
// This code is contributed by target_2

<script>
// Javascript program for the above approach
 
// Function to find the maximum
// and minimum number of elements
// whose sum is less than equal
// to K
function findMinMax(arr, N, K) {
  // Sorting both arrays
  arr.sort();
 
  // To store the minimum and maximum
  // number of elements whose sum is
  // less than equal to K
  let maxNumEle = 0;
  let minNumEle = 0;
 
  // Store the cumulative sum
  let i,
    cumSum1 = 0;
 
  // Iterate in the range [0, N-1]
  for (i = 0; i < N; i++) {
    cumSum1 += arr[i];
 
    // If cumSum1 is less than K
    if (cumSum1 <= K) maxNumEle += 1;
    else break;
  }
  // Store the cumulative sum
  let cumSum2 = 0;
 
  // Iterate in the range [N-1, 0]
  for (i = N - 1; i >= 0; i--) {
    cumSum2 += arr[i];
 
    // If cumSum2 is less than K
    if (cumSum2 <= K) minNumEle += 1;
    else break;
  }
  // Print the value of maxNumEle and minNumEle
  document.write(maxNumEle + " " + minNumEle);
}
// Driver Code
 
// Given Input
let N = 4;
let K = 7;
let arr = [6, 2, 1, 3];
 
// Function Call
findMinMax(arr, N, K);
 
// This code is contributed by gfgking
 
</script>

3 1

Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)