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 itvoid 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 codeint 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 itfunction 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 codevar 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.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
