Verifique si la array dada se puede reducir a 0 eliminando el elemento menor que K y agregándolo a K

Dada una array, arr[] de tamaño N y un entero K. Si un valor en arr[] es menor o igual que K , ese valor se eliminará de la array y se agregará a K . La tarea es verificar si todos los elementos en arr[] pueden ser absorbidos o no. 

Ejemplos:

Entrada: K = 10, arr[] = {3, 9, 19, 5, 21}
Salida: verdadero
Explicación: Los elementos de la array se absorben de la siguiente manera.
Una forma de absorción es {9, 19, 5, 3, 21}
el valor es 9 y el nuevo valor k: 10 + 9 = 19
el valor es 19 y el nuevo valor k: 19 + 19 = 38
el valor es 5 y el nuevo valor k: 38 + 5 = 43
el valor es 3 y el nuevo valor k: 43 + 3 = 46
el valor es 9 y el nuevo valor k: 46 + 21 = 6. 
Por lo tanto, todos los valores se absorben.

Entrada: K = 5, arr[] = {4, 9, 23, 4}
Salida: falso

Enfoque: este problema se puede resolver utilizando el enfoque codicioso . Siga los pasos a continuación para resolver el problema dado. 

• Cualquier elemento en arr[] que tenga la mayor probabilidad de ser menor o igual que K sería el elemento más pequeño.
• Por lo tanto, ordene la array en orden no decreciente e intente eliminar elementos de izquierda a derecha.
• Iterar de izquierda a derecha mientras elimina valores de arr[] .
• En cualquier momento, si no es posible eliminar ningún elemento, devuelve falso .
• De lo contrario, devuelve verdadero .

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

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if all the elements
// can be absorbed or not
bool absorbption(int K, vector<int>& arr)
{
 
    // Sort the array in non-decreasing order
    sort(arr.begin(), arr.end());
 
    // Long long  prevent from integer overflow
    long long m = K;
 
    for (int i = 0; i < arr.size(); i++) {
        int value = arr[i];
        if (m < value) {
            return false;
        }
        else {
            m += arr[i];
        }
    }
    return true;
}
 
// Driver Code
int main()
{
    vector<int> arr{ 3, 9, 19, 5, 21 };
    int K = 10;
 
    // Check if all the elements
    // can be removed or not.
    if (absorbption(K, arr))
        cout << "true";
    else
        cout << "false";
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
 
  // Function to check if all the elements
  // can be absorbed or not
  static  Boolean absorbption(int K, int arr[ ])
  {
 
    // Sort the array in non-decreasing order
    Arrays.sort(arr);
 
    // Long long  prevent from integer overflow
    long m = K;
 
    for (int i = 0; i < arr.length; i++) {
      int value = arr[i];
      if (m < value) {
        return false;
      }
      else {
        m += arr[i];
      }
    }
    return true;
  }
 
  public static void main (String[] args) {
    int arr[ ] = { 3, 9, 19, 5, 21 };
    int K = 10;
 
    // Check if all the elements
    // can be removed or not.
    if (absorbption(K, arr))
      System.out.print("true");
    else
      System.out.print("false");
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python 3 program for above approach
 
# Function to check if all the elements
# can be absorbed or not
def absorbption(K, arr):
 
    # Sort the array in non-decreasing order
    arr.sort()
 
    # Long long  prevent from integer overflow
    m = K
 
    for i in range(len(arr)):
        value = arr[i]
        if (m < value):
            return False
 
        else:
            m += arr[i]
 
    return True
 
# Driver Code
if __name__ == "__main__":
 
    arr = [3, 9, 19, 5, 21]
    K = 10
 
    # Check if all the elements
    # can be removed or not.
    if (absorbption(K, arr)):
        print("true")
    else:
        print("false")
 
        # This code is contributed by ukasp.

// C# program for the above approach
using System;
class GFG
{
 
  // Function to check if all the elements
  // can be absorbed or not
  static bool absorbption(int K, int []arr)
  {
 
    // Sort the array in non-decreasing order
    Array.Sort(arr);
 
    // Long long  prevent from integer overflow
    long m = K;
 
    for (int i = 0; i < arr.Length; i++) {
      int value = arr[i];
      if (m < value) {
        return false;
      }
      else {
        m += arr[i];
      }
    }
    return true;
  }
 
  // Driver Code
  public static void Main()
  {
    int []arr = { 3, 9, 19, 5, 21 };
    int K = 10;
 
    // Check if all the elements
    // can be removed or not.
    if (absorbption(K, arr))
      Console.Write("true");
    else
      Console.Write("false");
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
       // Function to check if all the elements
       // can be absorbed or not
       function absorbption(K, arr) {
 
           // Sort the array in non-decreasing order
           arr.sort(function (a, b) { return a - b })
           let m = K;
 
           for (let i = 0; i < arr.length; i++) {
               let value = arr[i];
               if (m < value) {
                   return false;
               }
               else {
                   m += arr[i];
               }
           }
           return true;
       }
 
       // Driver Code
 
       let arr = [3, 9, 19, 5, 21];
       let K = 10;
 
       // Check if all the elements
       // can be removed or not.
       if (absorbption(K, arr))
           document.write("true");
       else
           document.write("false");
 
 // This code is contributed by Potta Lokesh
   </script>

true

Complejidad de tiempo: O(N * logN)
Espacio auxiliar: O(1)