Given an integer K and two arrays A[] and B[] consisting of N and M integers, the task is to maximize the number of elements that can be removed from the front of either array according to the following rules:
- Remove an element from the front of either array A[] and B[] such that the value of the removed element must be at most K.
- Decrease the value of K by the value of the element removed.
Examples:
Input: K = 7, A[] = {2, 4, 7, 3}, B[] = {1, 9, 3, 4, 5}
Output: 3
Explanation:
Operation 1: Choose element from the array A[] and decrease K by A[0](=2), then value of K becomes = (7 – 2) = 5.
Operation 2: Choose element from the array B[] and decrease K by B[0](=1), then value of K becomes = (5 – 1) = 4.
Operation 3: Choose element from the array A[] and decrease K by A[1](=4), then value of K becomes = (4 – 4) = 4.
After the above operations, no more element can be removed. Therefore, print 3.Input: K = 9, A[] = {12, 10, 1, 2, 3}, B[] = {15, 19, 3, 4, 5}
Output: 0
Approach: The given problem can be solved by using the Prefix Sum and Binary Search to find the total items possible j to take from stack B after taking i items from stack A and return the result as the maximum value of (i + j). Follow the below steps to solve the given problem:
- Find prefix sum of the arrays A[] and B[].
- Initialize a variable, say count as 0, that stores the maximum items that can be taken.
- Traverse the array, A[] over the range [0, N] using the variable i and perform the following steps:
- If the value of A[i] is greater than K, then break out of the loop.
- Store the remaining amount after taking i items from stack A in a variable, rem as K – A[i].
- Perform a binary search on the array B, to find the maximum items say, j that can be taken in rem amount from stack B (after taking i elements from stack A).
- Store the maximum value of i + j in the variable count.
- After completing the above steps, print the value of count as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum number// of items that can be removed from// both the arraysvoid maxItems(int n, int m, int a[], int b[], int K){ // Stores the maximum item count int count = 0; // Stores the prefix sum of the // cost of items int A[n + 1]; int B[m + 1]; // Insert the item cost 0 at the // front of the arrays A[0] = 0; B[0] = 0; // Build the prefix sum for // the array A[] for (int i = 1; i <= n; i++) { // Update the value of A[i] A[i] = a[i - 1] + A[i - 1]; } // Build the prefix sum for // the array B[] for (int i = 1; i <= m; i++) { // Update the value of B[i] B[i] = b[i - 1] + B[i - 1]; } // Iterate through each item // of the array A[] for (int i = 0; i <= n; i++) { // If A[i] exceeds K if (A[i] > K) break; // Store the remaining amount // after taking top i elements // from the array A int rem = K - A[i]; // Store the number of items // possible to take from the // array B[] int j = 0; // Store low and high bounds // for binary search int lo = 0, hi = m; // Binary search to find // number of item that // can be taken from stack // B in rem amount while (lo <= hi) { // Calculate the mid value int mid = (lo + hi) / 2; if (B[mid] <= rem) { // Update the value // of j and lo j = mid; lo = mid + 1; } else { // Update the value // of the hi hi = mid - 1; } } // Store the maximum of total // item count count = max(j + i, count); } // Print the result cout << count;}// Driver Codeint main(){ int n = 4, m = 5, K = 7; int A[n] = { 2, 4, 7, 3 }; int B[m] = { 1, 9, 3, 4, 5 }; maxItems(n, m, A, B, K); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{// Function to find the maximum number// of items that can be removed from// both the arraysstatic void maxItems(int n, int m, int a[], int b[], int K){ // Stores the maximum item count int count = 0; // Stores the prefix sum of the // cost of items int A[] = new int[n + 1]; int B[] = new int[m + 1]; // Insert the item cost 0 at the // front of the arrays A[0] = 0; B[0] = 0; // Build the prefix sum for // the array A[] for(int i = 1; i <= n; i++) { // Update the value of A[i] A[i] = a[i - 1] + A[i - 1]; } // Build the prefix sum for // the array B[] for(int i = 1; i <= m; i++) { // Update the value of B[i] B[i] = b[i - 1] + B[i - 1]; } // Iterate through each item // of the array A[] for(int i = 0; i <= n; i++) { // If A[i] exceeds K if (A[i] > K) break; // Store the remaining amount // after taking top i elements // from the array A int rem = K - A[i]; // Store the number of items // possible to take from the // array B[] int j = 0; // Store low and high bounds // for binary search int lo = 0, hi = m; // Binary search to find // number of item that // can be taken from stack // B in rem amount while (lo <= hi) { // Calculate the mid value int mid = (lo + hi) / 2; if (B[mid] <= rem) { // Update the value // of j and lo j = mid; lo = mid + 1; } else { // Update the value // of the hi hi = mid - 1; } } // Store the maximum of total // item count count = Math.max(j + i, count); } // Print the result System.out.print(count);}// Driver Codepublic static void main (String[] args){ int n = 4, m = 5, K = 7; int A[] = { 2, 4, 7, 3 }; int B[] = { 1, 9, 3, 4, 5 }; maxItems(n, m, A, B, K);}}// This code is contributed by sanjoy_62 |
Python3
# Python3 program for the above approach# Function to find the maximum number# of items that can be removed from# both the arraysdef maxItems(n, m, a, b, K): # Stores the maximum item count count = 0 # Stores the prefix sum of the # cost of items A = [0 for i in range(n + 1)] B = [0 for i in range(m + 1)] # Build the prefix sum for # the array A[] for i in range(1, n + 1, 1): # Update the value of A[i] A[i] = a[i - 1] + A[i - 1] # Build the prefix sum for # the array B[] for i in range(1, m + 1, 1): # Update the value of B[i] B[i] = b[i - 1] + B[i - 1] # Iterate through each item # of the array A[] for i in range(n + 1): # If A[i] exceeds K if (A[i] > K): break # Store the remaining amount # after taking top i elements # from the array A rem = K - A[i] # Store the number of items # possible to take from the # array B[] j = 0 # Store low and high bounds # for binary search lo = 0 hi = m # Binary search to find # number of item that # can be taken from stack # B in rem amount while (lo <= hi): # Calculate the mid value mid = (lo + hi) // 2 if (B[mid] <= rem): # Update the value # of j and lo j = mid lo = mid + 1 else: # Update the value # of the hi hi = mid - 1 # Store the maximum of total # item count count = max(j + i, count) # Print the result print(count)# Driver Codeif __name__ == '__main__': n = 4 m = 5 K = 7 A = [ 2, 4, 7, 3 ] B = [ 1, 9, 3, 4, 5 ] maxItems(n, m, A, B, K) # This code is contributed by bgangwar59 |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the maximum number// of items that can be removed from// both the arraysstatic void maxItems(int n, int m, int[] a, int[] b, int K){ // Stores the maximum item count int count = 0; // Stores the prefix sum of the // cost of items int[] A = new int[n + 1]; int[] B= new int[m + 1]; // Insert the item cost 0 at the // front of the arrays A[0] = 0; B[0] = 0; // Build the prefix sum for // the array A[] for(int i = 1; i <= n; i++) { // Update the value of A[i] A[i] = a[i - 1] + A[i - 1]; } // Build the prefix sum for // the array B[] for(int i = 1; i <= m; i++) { // Update the value of B[i] B[i] = b[i - 1] + B[i - 1]; } // Iterate through each item // of the array A[] for(int i = 0; i <= n; i++) { // If A[i] exceeds K if (A[i] > K) break; // Store the remaining amount // after taking top i elements // from the array A int rem = K - A[i]; // Store the number of items // possible to take from the // array B[] int j = 0; // Store low and high bounds // for binary search int lo = 0, hi = m; // Binary search to find // number of item that // can be taken from stack // B in rem amount while (lo <= hi) { // Calculate the mid value int mid = (lo + hi) / 2; if (B[mid] <= rem) { // Update the value // of j and lo j = mid; lo = mid + 1; } else { // Update the value // of the hi hi = mid - 1; } } // Store the maximum of total // item count count = Math.Max(j + i, count); } // Print the result Console.Write(count);}// Driver codepublic static void Main(String []args){ int n = 4, m = 5, K = 7; int[] A = { 2, 4, 7, 3 }; int[] B = { 1, 9, 3, 4, 5 }; maxItems(n, m, A, B, K);}}// This code is contributed by code_hunt. |
Javascript
<script>// javascript program for the above approach// Function to find the maximum number// of items that can be removed from// both the arraysfunction maxItems(n, m, a, b, K){ // Stores the maximum item count var count = 0; // Stores the prefix sum of the // cost of items var A = new Array(n + 1); var B = new Array(m + 1); // Insert the item cost 0 at the // front of the arrays A[0] = 0; B[0] = 0; var i; // Build the prefix sum for // the array A[] for (i = 1; i <= n; i++) { // Update the value of A[i] A[i] = a[i - 1] + A[i - 1]; } // Build the prefix sum for // the array B[] for (i = 1; i <= m; i++) { // Update the value of B[i] B[i] = b[i - 1] + B[i - 1]; } // Iterate through each item // of the array A[] for (i = 0; i <= n; i++) { // If A[i] exceeds K if (A[i] > K) break; // Store the remaining amount // after taking top i elements // from the array A var rem = K - A[i]; // Store the number of items // possible to take from the // array B[] var j = 0; // Store low and high bounds // for binary search var lo = 0, hi = m; // Binary search to find // number of item that // can be taken from stack // B in rem amount while (lo <= hi) { // Calculate the mid value var mid = parseInt((lo + hi) / 2); if (B[mid] <= rem) { // Update the value // of j and lo j = mid; lo = mid + 1; } else { // Update the value // of the hi hi = mid - 1; } } // Store the maximum of total // item count count = Math.max(j + i, count); } // Print the result document.write(count);}// Driver Code var n = 4, m = 5, K = 7; var A = [2, 4, 7, 3]; var B = [1, 9, 3, 4, 5]; maxItems(n, m, A, B, K);// This code is contributed by SURENDRA_GANGWAR.</script> |
Output
3
Time Complexity: O(N * log(M))
Auxiliary Space: O(N + M)
Approach(Space Optimization): This approach sorts both arrays in ascending order and then uses two pointers to traverse the arrays from both ends. The idea is to pair the smallest element of array A with the largest element of array B that has not yet been paired.
Step-by-step algorithm:
- Sort both arrays a[] and b[] in non-decreasing order.
- Initialize two variables i and j to 0 and m-1 respectively.
- Initialize a count variable to 0.
- Repeat the following until either i >= n or j < 0:
a. If a[i]+b[j] <= K, then increment the count variable and increment i and decrement j.
b. Else if a[i]+b[j] > K and j > 0, then decrement j.
c. Else, increment i. - Print the value of the count variable.
C++
#include <bits/stdc++.h>using namespace std;void maxItems(int n, int m, int a[], int b[], int K) { sort(a, a + n); sort(b, b + m); int i = 0, j = m - 1, count = 0; while (i < n && j >= 0) { if (a[i] + b[j] <= K) { count++; i++; j--; } else if (a[i] + b[j] > K && j > 0) { j--; } else { i++; } } cout << count << endl;}int main() { int n = 4, m = 5, K = 7; int A[n] = {2, 4, 7, 3}; int B[m] = {1, 9, 3, 4, 5}; maxItems(n, m, A, B, K); return 0;} |
Java
import java.util.Arrays;public class MaxItems { public static void maxItems(int n, int m, int[] a, int[] b, int K) { Arrays.sort(a); // Sort array a in ascending order Arrays.sort(b); // Sort array b in ascending order int i = 0, j = m - 1, count = 0; while (i < n && j >= 0) { if (a[i] + b[j] <= K) { // If sum of elements at a[i] and b[j] is less than or equal to K count++; i++; j--; } else if (a[i] + b[j] > K && j > 0) { // If sum is greater than K and there are elements left in array b j--; } else { i++; // Increment index of array a } } System.out.println(count); // Print the count of valid pairs } public static void main(String[] args) { int n = 4, m = 5, K = 7; int[] A = {2, 4, 7, 3}; int[] B = {1, 9, 3, 4, 5}; maxItems(n, m, A, B, K); }} |
Python3
# Added by: Nikunj Sonigaradef max_items(n, m, a, b, K): a.sort() b.sort() i = 0 j = m - 1 count = 0 while i < n and j >= 0: if a[i] + b[j] <= K: count += 1 i += 1 j -= 1 elif a[i] + b[j] > K and j > 0: j -= 1 else: i += 1 print(count)if __name__ == "__main__": n = 4 m = 5 K = 7 A = [2, 4, 7, 3] B = [1, 9, 3, 4, 5] max_items(n, m, A, B, K) |
C#
using System;public class MaxItems{ public static void FindMaxItems(int n, int m, int[] a, int[] b, int K) { Array.Sort(a); // Sort array a in ascending order Array.Sort(b); // Sort array b in ascending order int i = 0, j = m - 1, count = 0; while (i < n && j >= 0) { if (a[i] + b[j] <= K) // If sum of elements at a[i] and b[j] is less than or equal to K { count++; i++; j--; } else if (a[i] + b[j] > K && j > 0) // If sum is greater than K and there are elements left in array b { j--; } else { i++; // Increment index of array a } } Console.WriteLine(count); // Print the count of valid pairs } public static void Main(string[] args) { int n = 4, m = 5, K = 7; int[] A = { 2, 4, 7, 3 }; int[] B = { 1, 9, 3, 4, 5 }; FindMaxItems(n, m, A, B, K); }} |
Javascript
// Added by: Nikunj Sonigarafunction maxItems(n, m, a, b, K) { a.sort((x, y) => x - y); b.sort((x, y) => x - y); let i = 0; let j = m - 1; let count = 0; while (i < n && j >= 0) { if (a[i] + b[j] <= K) { count++; i++; j--; } else if (a[i] + b[j] > K && j > 0) { j--; } else { i++; } } console.log(count);}const n = 4;const m = 5;const K = 7;const A = [2, 4, 7, 3];const B = [1, 9, 3, 4, 5];maxItems(n, m, A, B, K); |
Output
3
Time Complexity: O(N log N + M log M)
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!
