Given two arrays arr[] and brr[] of size N and M respectively, the task is to count the maximum number of elements that can be removed from the array arr[] such that the sum of elements in arr[] is greater than or equal to the sum of elements in brr[].
Examples:
Input: arr[] = { 1, 2, 4, 6 }, brr[] = { 7 }
Output: 2
Explanation:
Removing arr[2] modifies arr[] to { 1, 2, 6 } and sum equal to 9 (> 7)
Removing arr[1] modifies arr[] to { 1, 6 } and sum equal to 7 (&gr; 7)
Removing arr[0] modifies arr[] to { 6 } and sum equal to 6 (< 7)
Therefore, the required output is 2.Input: arr[] = { 10, 20 }, brr[] = { 5 }
Output: 1
Explanation:
Removing arr[1] modifies arr[] to { 10 } and sum equal to 10 (> 5)
Removing arr[0] modifies arr[] to { } and sum equal to 0 (< 5)
Therefore, the required output is 1.
Approach: The problem can be solved using Greedy technique. Follow the steps below to solve the problem:
- Sort the array, arr[] in ascending order.
- Remove the smallest element from the array arr[] and check if the sum of elements of arr[] is greater than or equal to sum of array elements brr[] or not. If found to be true, then increment the count.
- Finally, print the count obtained.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to maximize the count of elements// required to be removed from arr[] such that// the sum of arr[] is greater than or equal// to sum of the array brr[]int maxCntRemovedfromArray(int arr[], int N, int brr[], int M){ // Sort the array arr[] sort(arr, arr + N); // Stores index of smallest // element of arr[] int i = 0; // Stores sum of elements // of the array arr[] int sumArr = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Update sumArr sumArr += arr[i]; } // Stores sum of elements // of the array brr[] int sumBrr = 0; // Traverse the array brr[] for (int i = 0; i < M; i++) { // Update sumArr sumBrr += brr[i]; } // Stores count of // removed elements int cntRemElem = 0; // Repeatedly remove the smallest // element of arr[] while (i < N and sumArr >= sumBrr) { // Update sumArr sumArr -= arr[i]; // Remove the smallest element i += 1; // If the sum of remaining elements // in arr[] >= sum of brr[] if (sumArr >= sumBrr) { // Update cntRemElem cntRemElem += 1; } } return cntRemElem;}// Driver Codeint main(){ int arr[] = { 1, 2, 4, 6 }; int brr[] = { 7 }; int N = sizeof(arr) / sizeof(arr[0]); int M = sizeof(brr) / sizeof(brr[0]); cout << maxCntRemovedfromArray(arr, N, brr, M);} |
Java
// Java program to implement// the above approachimport java.io.*;import java.util.*;class GFG { // Function to maximize the count of elements // required to be removed from arr[] such that // the sum of arr[] is greater than or equal // to sum of the array brr[] static int maxCntRemovedfromArray(int[] arr, int N, int[] brr, int M) { // Sort the array arr[] Arrays.sort(arr); // Stores index of smallest // element of arr[] int i = 0; // Stores sum of elements // of the array arr[] int sumArr = 0; // Traverse the array arr[] for (i = 0; i < N; i++) { // Update sumArr sumArr += arr[i]; } // Stores sum of elements // of the array brr[] int sumBrr = 0; // Traverse the array brr[] for (i = 0; i < M; i++) { // Update sumArr sumBrr += brr[i]; } // Stores count of // removed elements int cntRemElem = 0; // Repeatedly remove the smallest // element of arr[] while (i < N && sumArr >= sumBrr) { // Update sumArr sumArr -= arr[i]; // Remove the smallest element i += 1; // If the sum of remaining elements // in arr[] >= sum of brr[] if (sumArr >= sumBrr) { // Update cntRemElem cntRemElem += 1; } } return cntRemElem; } // Driver Code public static void main(String[] args) { int[] arr = new int[] { 1, 2, 4, 6 }; int[] brr = new int[] { 7 }; int N = arr.length; int M = brr.length; System.out.println( maxCntRemovedfromArray(arr, N, brr, M)); }}// This code is contributed by Dharanendra L V |
Python3
# Python3 program to implement# the above approach# Function to maximize the count of elements# required to be removed from arr[] such that# the sum of arr[] is greater than or equal# to sum of the array brr[]def maxCntRemovedfromArray(arr, N, brr, M): # Sort the array arr[] arr.sort(reverse = False) # Stores index of smallest # element of arr[] i = 0 # Stores sum of elements # of the array arr[] sumArr = 0 # Traverse the array arr[] for i in range(N): # Update sumArr sumArr += arr[i] # Stores sum of elements # of the array brr[] sumBrr = 0 # Traverse the array brr[] for i in range(M): # Update sumArr sumBrr += brr[i] # Stores count of # removed elements cntRemElem = 0 # Repeatedly remove the smallest # element of arr[] while (i < N and sumArr >= sumBrr): # Update sumArr sumArr -= arr[i] # Remove the smallest element i += 1 # If the sum of remaining elements # in arr[] >= sum of brr[] if (sumArr >= sumBrr): # Update cntRemElem cntRemElem += 1 return cntRemElem# Driver Codeif __name__ == '__main__': arr = [ 1, 2, 4, 6 ] brr = [7] N = len(arr) M = len(brr) print(maxCntRemovedfromArray(arr, N, brr, M))# This code is contributed by SURENDRA_GANGWAR |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to maximize the count of elements // required to be removed from arr[] such that // the sum of arr[] is greater than or equal // to sum of the array brr[] static int maxCntRemovedfromArray(int[] arr, int N, int[] brr, int M) { // Sort the array arr[] Array.Sort(arr); // Stores index of smallest // element of arr[] int i = 0; // Stores sum of elements // of the array arr[] int sumArr = 0; // Traverse the array arr[] for (i = 0; i < N; i++) { // Update sumArr sumArr += arr[i]; } // Stores sum of elements // of the array brr[] int sumBrr = 0; // Traverse the array brr[] for (i = 0; i < M; i++) { // Update sumArr sumBrr += brr[i]; } // Stores count of // removed elements int cntRemElem = 0; // Repeatedly remove the smallest // element of arr[] while (i < N && sumArr >= sumBrr) { // Update sumArr sumArr -= arr[i]; // Remove the smallest element i += 1; // If the sum of remaining elements // in arr[] >= sum of brr[] if (sumArr >= sumBrr) { // Update cntRemElem cntRemElem += 1; } } return cntRemElem; } // Driver Code static public void Main() { int[] arr = new int[] { 1, 2, 4, 6 }; int[] brr = new int[] { 7 }; int N = arr.Length; int M = brr.Length; Console.WriteLine( maxCntRemovedfromArray(arr, N, brr, M)); }}// This code is contributed by Dharanendra L V |
Javascript
<script>// Javascript program of the above approach // Function to maximize the count of elements // required to be removed from arr[] such that // the sum of arr[] is greater than or equal // to sum of the array brr[] function maxCntRemovedfromArray(arr, N, brr, M) { // Sort the array arr[] arr.sort(); // Stores index of smallest // element of arr[] let i = 0; // Stores sum of elements // of the array arr[] let sumArr = 0; // Traverse the array arr[] for (i = 0; i < N; i++) { // Update sumArr sumArr += arr[i]; } // Stores sum of elements // of the array brr[] let sumBrr = 0; // Traverse the array brr[] for (i = 0; i < M; i++) { // Update sumArr sumBrr += brr[i]; } // Stores count of // removed elements let cntRemElem = 0; // Repeatedly remove the smallest // element of arr[] while (i < N && sumArr >= sumBrr) { // Update sumArr sumArr -= arr[i]; // Remove the smallest element i += 1; // If the sum of remaining elements // in arr[] >= sum of brr[] if (sumArr >= sumBrr) { // Update cntRemElem cntRemElem += 1; } } return cntRemElem; } // Driver Code let arr = [ 1, 2, 4, 6 ]; let brr = [ 7 ]; let N = arr.length; let M = brr.length; document.write( maxCntRemovedfromArray(arr, N, brr, M) ); </script> |
Output:
2
Time Complexity: O(N * log(N))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
