Empty an Array by removing maximum of K value from it
Given an array arr of size N and a value K, the task is to empty this array by removing a maximum of K from it. Print the value removed if the array was emptied, else -1.
Examples:
Input: arr[] = {2, 2}, K = 5
Output: 4
Explanation:
After removing arr[1] (=2) from K (=5), K = 5 – 2 = 3
After removing arr[2] (=2) from K (=3), K = 3 – 2 = 1
Since the array has been emptied and K is still > 0
Therefore the value removed = 2 + 2 = 4
Input: arr[] = {5, 3, 2, 2}, K = 10
Output: -1
Explanation:
After removing arr[1] (=5) from K (=10), K = 10 – 5 = 5
After removing arr[2] (=3) from K (=5), K = 5 – 3 = 2
After removing arr[3] (=2) from K (=2), K = 2 – 2 = 0
After removing arr[4] (=2) from K (=0), K = 0 – 2 = -2
Since the array has been emptied and K is < 0
Therefore the array cannot be emptied for this K
hence the output is -1
Approach:
- The given problem can be observed as finding the total sum of the array arr and removing this sum from K.
- If this sum is less than or equal to K, then the array can be emptied and the output will be the sum of the array.
- Else the output will be -1.
Below is the implementation of the above approach:
C++
// C++ program to empty an Array // by removing a maximum of K value from it #include <bits/stdc++.h> using namespace std; // Function to Empty an Array by removing // maximum of K value from it void emptyArray( long long int n, long long int k, long long int arr[]) { long long int sum = 0, i; // Find the total sum of the array for (i = 0; i < n; i++) sum += arr[i]; // Find if sum is less than or equal to K if (sum <= k) cout << sum << "\n" ; else cout << -1 << "\n" ; } // Driver code int main() { long long int n = 2, k = 5; long long int arr[] = { 2, 2 }; emptyArray(n, k, arr); n = 4, k = 10; long long int arr1[] = { 5, 3, 2, 2 }; emptyArray(n, k, arr1); return 0; } |
Java
// Java program to empty an Array // by removing a maximum of K value from it class GFG { // Function to Empty an Array by removing // maximum of K value from it static void emptyArray( int n, int k, int arr[]) { int sum = 0 , i; // Find the total sum of the array for (i = 0 ; i < n; i++) sum += arr[i]; // Find if sum is less than or equal to K if (sum <= k) System.out.println(sum); else System.out.println(- 1 ); } // Driver code public static void main (String[] args) { int n = 2 ; int k = 5 ; int arr[] = { 2 , 2 }; emptyArray(n, k, arr); n = 4 ; k = 10 ; int arr1[] = { 5 , 3 , 2 , 2 }; emptyArray(n, k, arr1); } } // This code is contributed by AnkitRai01 |
Python3
# Python program to empty an Array # by removing a maximum of K value from it # Function to Empty an Array by removing # maximum of K value from it def emptyArray(n, k, arr) : sum = 0 ; # Find the total sum of the array for i in range (n) : sum + = arr[i]; # Find if sum is less than or equal to K if ( sum < = k) : print ( sum ); else : print ( - 1 ); # Driver code if __name__ = = "__main__" : n = 2 ; k = 5 ; arr = [ 2 , 2 ]; emptyArray(n, k, arr); n = 4 ; k = 10 ; arr1 = [ 5 , 3 , 2 , 2 ]; emptyArray(n, k, arr1); # This code is contributed by AnkitRai01 |
C#
// C# program to empty an Array // by removing a maximum of K value from it using System; class GFG { // Function to Empty an Array by removing // maximum of K value from it static void emptyArray( int n, int k, int []arr) { int sum = 0, i; // Find the total sum of the array for (i = 0; i < n; i++) sum += arr[i]; // Find if sum is less than or equal to K if (sum <= k) Console.WriteLine(sum); else Console.WriteLine(-1); } // Driver code public static void Main(String[] args) { int n = 2; int k = 5; int []arr = { 2, 2 }; emptyArray(n, k, arr); n = 4; k = 10; int []arr1 = { 5, 3, 2, 2 }; emptyArray(n, k, arr1); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript program to empty an Array // by removing a maximum of K value from it // Function to Empty an Array by removing // maximum of K value from it function emptyArray(n, k, arr) { var sum = 0, i; // Find the total sum of the array for (i = 0; i < n; i++) sum += arr[i]; // Find if sum is less than or equal to K if (sum <= k) document.write( sum + "<br>" ); else document.write( -1 ); } // Driver code var n = 2, k = 5; var arr = [2, 2]; emptyArray(n, k, arr); var n = 4, k = 10; var arr1 = [5, 3, 2, 2]; emptyArray(n, k, arr1); </script> |
4 -1
Time Complexity: O(n), Here n is the number of elements in the array.
Auxiliary Space: O(1), As constant extra space is used.
Contact Us