Given two arrays S1 and S2 containing N and M integers, and an integer K, the task is to find the maximum number of integers that can be removed from end of either given arrays, such that the sum of removed elements is less than or equal to K.
Example:
Input: S1[] = {1, 2, 3}, S2[] = {1, 2, 4}, K = 10
Output: 5
Explanation: All the elements of S1 i.e, {1, 2, 3} and two elements of S2 i.e, {1, 2} can be removed from the given arrays as their sum is 9 which is less than 10. Hence, the number of integers that can be removes is 5 which is the maximum possible.Input: S1[] = {12, 21, 102}, S2[] = {167, 244, 377, 56, 235, 269, 23}, K = 1000
Output: 7
Approach: The above approach can be solved with the help of a greedy approach. The idea is to consider the given arrays as stacks (as only the endmost element can be removed from any array). Check over all possible valid sequences of operations using a two-pointer approach. Below are the steps to follow:
- First, check how many numbers of S1 can be obtained considering S2 does not exist.
- Now, the current answer obtained in step 1 is stored as the final answer.
- Now start traversing S2 and keep inserting the elements in the set of removed integers. If the sum of removed elements exceeds K at any point, remove the integers of S1 that are included from the last until the sum is less than or equal to K.
- Update the final answer according to the current answer in each step which is actually giving all possible valid sequences of operations.
Below is the implementation of the above approach:
C++
// C++ program of the above approach #include <bits/stdc++.h> using namespace std; // Function to return max profit // from both stacks given as input int Max_profit_maximisation(int Stack1[], int Stack2[], int n, int m, int K) { // Stores the final answer int maximum_result = 0; // Stores the pointer to the // current window in stack 1 int index_for_Stack1 = 0; // Stores the pointer to the // current window in stack 2 int index_for_Stack2; // Stores sum of current window int curr_sum = 0; // Case where snly stack 1 // is considered while (index_for_Stack1 < n && curr_sum + Stack1[index_for_Stack1] < K) { curr_sum += Stack1[index_for_Stack1]; index_for_Stack1++; } // Update answer maximum_result = index_for_Stack1; // Traverse Stack 2 and insert // elements into the current // window one at a time while (index_for_Stack2 < m) { curr_sum += Stack2[index_for_Stack2]; index_for_Stack2++; // curr_sum after removing // last elements from Stack1 while (curr_sum > K && index_for_Stack1 > 0) { index_for_Stack1--; curr_sum -= Stack1[index_for_Stack1]; } // Updating the answer maximum_result = max(maximum_result, index_for_Stack1 + index_for_Stack2); } // Return Answer return maximum_result; } // Driver code int main() { int S1[] = { 12, 21, 102 }; int S2[] = { 167, 244, 377, 56, 235, 269, 23 }; int N = 3; int M = 7; int K = 1000; cout << Max_profit_maximisation(S1, S2, N, M, K); return 0; } |
Java
// Java program of the above approach import java.util.*; class GFG{ // Function to return max profit // from both stacks given as input static int Max_profit_maximisation(int Stack1[], int Stack2[], int n, int m, int K) { // Stores the final answer int maximum_result = 0; // Stores the pointer to the // current window in stack 1 int index_for_Stack1 =0; // Stores the pointer to the // current window in stack 2 int index_for_Stack2=Integer.MAX_VALUE; // Stores sum of current window int curr_sum = 0; // Case where snly stack 1 // is considered while (index_for_Stack1 < n && curr_sum + Stack1[index_for_Stack1] < K) { curr_sum += Stack1[index_for_Stack1]; index_for_Stack1++; } // Update answer maximum_result = index_for_Stack1; // Traverse Stack 2 and insert // elements into the current // window one at a time while (index_for_Stack2 < m) { curr_sum += Stack2[index_for_Stack2]; index_for_Stack2++; // curr_sum after removing // last elements from Stack1 while (curr_sum > K && index_for_Stack1 > 0) { index_for_Stack1--; curr_sum -= Stack1[index_for_Stack1]; } // Updating the answer maximum_result = Math.max(maximum_result, index_for_Stack1 + index_for_Stack2); } // Return Answer return maximum_result; } // Driver code public static void main(String[] args) { int S1[] = { 12, 21, 102 }; int S2[] = { 167, 244, 377, 56, 235, 269, 23 }; int N = 3; int M = 7; int K = 1000; System.out.print(Max_profit_maximisation(S1, S2, N, M, K)); } } // This code is contributed by shikhasingrajput |
Python
# Python program of the above approach # Function to return max profit # from both stacks given as input def Max_profit_maximisation(Stack1, Stack2, n, m, K): # Stores the final answer maximum_result = 0 # Stores the pointer to the # current window in stack 1 index_for_Stack1 = 0 # Stores the pointer to the # current window in stack 2 index_for_Stack2 = 100**100 # Stores sum of current window curr_sum = 0 # Case where snly stack 1 # is considered while (index_for_Stack1 < n and curr_sum + Stack1[index_for_Stack1] < K): curr_sum += Stack1[index_for_Stack1] index_for_Stack1 += 1 # Update answer maximum_result = index_for_Stack1 # Traverse Stack 2 and insert # elements into the current # window one at a time while (index_for_Stack2 < m) : curr_sum += Stack2[index_for_Stack2] index_for_Stack2 += 1 # curr_sum after removing # last elements from Stack1 while (curr_sum > K and index_for_Stack1 > 0): index_for_Stack1 -= 1 curr_sum -= Stack1[index_for_Stack1] # Updating the answer maximum_result = max(maximum_result, index_for_Stack1 + index_for_Stack2) # Return Answer return maximum_result # Driver Code if __name__ == '__main__': S1 = [ 12, 21, 102 ]; S2 = [ 167, 244, 377, 56, 235, 269, 23 ]; N = 3; M = 7; K = 1000; print(Max_profit_maximisation(S1, S2, N, M, K)) # This code is contributed by Samim Hossain Mondal. |
C#
// C# program of the above approach using System; class GFG{ // Function to return max profit // from both stacks given as input static int Max_profit_maximisation(int []Stack1, int []Stack2, int n, int m, int K) { // Stores the readonly answer int maximum_result = 0; // Stores the pointer to the // current window in stack 1 int index_for_Stack1 =0; // Stores the pointer to the // current window in stack 2 int index_for_Stack2=int.MaxValue; // Stores sum of current window int curr_sum = 0; // Case where snly stack 1 // is considered while (index_for_Stack1 < n && curr_sum + Stack1[index_for_Stack1] < K) { curr_sum += Stack1[index_for_Stack1]; index_for_Stack1++; } // Update answer maximum_result = index_for_Stack1; // Traverse Stack 2 and insert // elements into the current // window one at a time while (index_for_Stack2 < m) { curr_sum += Stack2[index_for_Stack2]; index_for_Stack2++; // curr_sum after removing // last elements from Stack1 while (curr_sum > K && index_for_Stack1 > 0) { index_for_Stack1--; curr_sum -= Stack1[index_for_Stack1]; } // Updating the answer maximum_result = Math.Max(maximum_result, index_for_Stack1 + index_for_Stack2); } // Return Answer return maximum_result; } // Driver code public static void Main(String[] args) { int []S1 = { 12, 21, 102 }; int []S2 = { 167, 244, 377, 56, 235, 269, 23 }; int N = 3; int M = 7; int K = 1000; Console.Write(Max_profit_maximisation(S1, S2, N, M, K)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript code for the above approach // Function to return max profit // from both stacks given as input function Max_profit_maximisation(Stack1, Stack2, n, m, K) { // Stores the final answer let maximum_result = 0; // Stores the pointer to the // current window in stack 1 let index_for_Stack1 = 0; // Stores the pointer to the // current window in stack 2 let index_for_Stack2; // Stores sum of current window let curr_sum = 0; // Case where snly stack 1 // is considered while (index_for_Stack1 < n && curr_sum + Stack1[index_for_Stack1] < K) { curr_sum += Stack1[index_for_Stack1]; index_for_Stack1++; } // Update answer maximum_result = index_for_Stack1; // Traverse Stack 2 and insert // elements into the current // window one at a time while (index_for_Stack2 < m) { curr_sum += Stack2[index_for_Stack2]; index_for_Stack2++; // curr_sum after removing // last elements from Stack1 while (curr_sum > K && index_for_Stack1 > 0) { index_for_Stack1--; curr_sum -= Stack1[index_for_Stack1]; } // Updating the answer maximum_result = Math.max(maximum_result, index_for_Stack1 + index_for_Stack2); } // Return Answer return maximum_result; } // Driver code let S1 = [12, 21, 102]; let S2 = [167, 244, 377, 56, 235, 269, 23]; let N = 3; let M = 7; let K = 1000; document.write(Max_profit_maximisation(S1, S2, N, M, K)); // This code is contributed by Potta Lokesh </script> |
Output
3
Time Complexity: O(N+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!
Share your thoughts in the comments
