Check if given Array can be reduced to 0 by removing element less than K and adding it to K - Coding

Given an array, arr[] of size N and an integer K. If a value in arr[] is less than or equal to K, then that value will be removed from the array and added to K. The task is to check if all the elements in arr[] can be absorbed or not.

Examples:

Input: K = 10, arr[] = {3, 9, 19, 5, 21}
Output: true
Explanation: The array elements are absorbed in following way.
One way to absorption is {9, 19, 5, 3, 21}
value is 9 and the New k value: 10 + 9 = 19
value is 19 and the New k value: 19 + 19 = 38
value is 5 and the New k value: 38 + 5 = 43
value is 3 and the New k value: 43 + 3 = 46
value is 9 and the New k value: 46 + 21 = 6.
Hence, All values are absorbed.

Input: K = 5, arr[] = {4, 9, 23, 4}
Output: false

Approach: This problem can be solved by using the Greedy Approach. Follow the steps below to solve the given problem.

Any element in arr[] that has the highest probability to be less than or equal to K would be the smallest element.
So, sort the array in non-decreasing order and try to remove elements from left to right.
Iterate from left to right while removing values of arr[].
At any time if it is not possible to remove any element, return false.
Else return true.

Below is the implementation of the above approach.

C++

// 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 absorption(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 (absorption(K, arr))
        cout << "true";
    else
        cout << "false";
    return 0;
}

Java

// 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 absorption(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 (absorption(K, arr))
      System.out.print("true");
    else
      System.out.print("false");
  }
}
 
// This code is contributed by hrithikgarg03188.

Python3

# Python 3 program for above approach
 
# Function to check if all the elements
# can be absorbed or not
def absorption(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 (absorption(K, arr)):
        print("true")
    else:
        print("false")
 
        # This code is contributed by ukasp.

C#

// C# program for the above approach
using System;
class GFG
{
 
  // Function to check if all the elements
  // can be absorbed or not
  static bool absorption(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 (absorption(K, arr))
      Console.Write("true");
    else
      Console.Write("false");
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
       // JavaScript code for the above approach 
 
       // Function to check if all the elements
       // can be absorbed or not
       function absorption(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 (absorption(K, arr))
           document.write("true");
       else
           document.write("false");
 
 // This code is contributed by Potta Lokesh
   </script>

Output

true

Time Complexity: O(N * logN)
Auxiliary Space: O(1)

Reffered: https://www.geeksforgeeks.org

Greedy

Related
Check if CPU will process given requests successfully or not
Minimal distance such that for every customer there is at least one vendor at given distance
Maximize the value left after reducing the Arrays based on given conditions
Minimize operations to convert (0, 0) to (N, M) by incrementing either or both by K
Count of rooks that can attack each other out of K rooks placed on a N*N chessboard

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	11