Given arrays A[] and B[] of size N and integer M, the task is to find out the minimum operations required to collect a sum of at least M by performing the following operations any number of times. Either choosing the first element of A[] or the first element of B[] remove that element from the front and add that to the sum. Initially, the sum is zero.
Examples:
Input: A[] = {1, 9, 1, 4, 0, 1}, B[] = {3, 2, 1, 5, 9, 10}, M = 12
Output: 3
Explanation: Initially sum = 0
- Removing front element of array A[] which is 1 and adding it to sum, now sum = 1.
- Removing front element of array A[] which is 9 again and adding it to sum, now sum = 10.
- Removing front element of array B[] which is 3 and adding it to sum, now sum = 13.
As 13 is greater than equal to M. Hence in three operations sum greater than equal to M = 12 can be achieved.
Input: A[] = {0, 1, 2, 3, 5}, B[] = {5, 0, 0, 0, 9}, M = 6
Output: 3
Naive approach: The basic way to solve the problem is as follows:
The basic way to solve this problem is to generate all possible combinations by using a recursive approach.
Time Complexity: O(2N)
Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following idea:
Dynamic programming can be used to solve this problem
- dp[i][j][k] represents a minimum number of operations to make at least i from the first j elements of array A[] and first k elements of array B[], Here i represents the amount to be made, j represents the jth element of A[] and k represents the kth element of B[].
- It can be observed that the recursive function is called exponential times. That means that some states are called repeatedly. So the idea is to store the value of each state.
- This can be done using by the store the value of a state and whenever the function is called, returning the stored value without computing again.
Follow the steps below to solve the problem:
- Create a recursive function that takes three parameters i represents the amount to be made, j represents the jth element of A[] and k represents k’th element of B[].
- Create a 3d array dp[M][N][N] initially filled with -1.
- If the answer for a particular state is computed then save it in dp[i][j][k].
- if the answer for a particular state is already computed then just return dp[i][j][k].
- Base case if i becomes zero return 0.
- Call the recursive function for choosing both the jth element of A[] and k’th element of B[].
- return the dp value by dp[i][j][k] = ans.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// dp table initialized with -1int dp[501][101][101];// Recursive Function to minimize the// operations to collect at least sum of Mint solve(int i, int j, int k, int A[], int B[], int N){ // Base case if (i <= 0) { return 0; } // If answer for current state is // already calculated then just // return dp[i][j][k] if (dp[i][j][k] != -1) return dp[i][j][k]; // Answer initialized with zero int ans = 1e9; // Calling recursive function for // taking j'th element of array A[] if (j != N) ans = min(ans, solve(i - A[j], j + 1, k, A, B, N) + 1); // Calling recursive function for // taking k'th element of array B[] if (k != N) ans = min(ans, solve(i - B[k], j, k + 1, A, B, N) + 1); // Save and return dp value return dp[i][j][k] = ans;}// Function to minimize the operations// to collect at least sum of Mint minOperations(int A[], int B[], int N, int M){ // Filling dp table with - 1 memset(dp, -1, sizeof(dp)); // Minimum operations int ans = solve(M, 0, 0, A, B, N); return ans;}// Driver Codeint main(){ // Input 1 int A[] = { 1, 9, 1, 4, 0, 1 }, B[] = { 3, 2, 1, 5, 9, 10 }; int N = sizeof(A) / sizeof(A[0]); int M = 12; // Function Call cout << minOperations(A, B, N, M) << endl; // Input 2 int A1[] = { 0, 1, 2, 3, 5 }, B1[] = { 5, 0, 0, 0, 9 }; int N1 = sizeof(A1) / sizeof(A1[0]); int M1 = 6; // Function Call cout << minOperations(A1, B1, N1, M1) << endl; return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // dp table initialized with -1 static int[][][] dp = new int[501][101][101]; // Recursive Function to minimize the // operations to collect at least sum of M static int solve(int i, int j, int k, int[] A, int[] B, int N) { // Base case if (i <= 0) { return 0; } // If answer for current state is // already calculated then just // return dp[i][j][k] if (dp[i][j][k] != -1) { return dp[i][j][k]; } // Answer initialized with zero int ans = (int)1e9; // Calling recursive function for // taking j'th element of array A[] if (j != N) { ans = Math.min( ans, solve(i - A[j], j + 1, k, A, B, N) + 1); } // Calling recursive function for // taking k'th element of array B[] if (k != N) { ans = Math.min( ans, solve(i - B[k], j, k + 1, A, B, N) + 1); } // Save and return dp value return dp[i][j][k] = ans; } // Function to minimize the operations // to collect at least sum of M static int minOperations(int[] A, int[] B, int N, int M) { // Filling dp table with - 1 for (int i = 0; i < dp.length; i++) { for (int j = 0; j < dp[i].length; j++) { Arrays.fill(dp[i][j], -1); } } // Minimum operations int ans = solve(M, 0, 0, A, B, N); return ans; } public static void main(String[] args) { // Input 1 int[] A = { 1, 9, 1, 4, 0, 1 }, B = { 3, 2, 1, 5, 9, 10 }; int N = A.length; int M = 12; // Function Call System.out.println(minOperations(A, B, N, M)); // Input 2 int[] A1 = { 0, 1, 2, 3, 5 }, B1 = { 5, 0, 0, 0, 9 }; int N1 = A1.length; int M1 = 6; // Function Call System.out.println(minOperations(A1, B1, N1, M1)); }}// This code is contributed by lokesh. |
Python3
# Python code for the above approachimport sysfrom typing import List# dp table initialized with -1dp = [[[-1 for _ in range(101)] for _ in range(101)] for _ in range(501)]def solve(i: int, j: int, k: int, A: List[int], B: List[int], N: int) -> int: # Base case if i <= 0: return 0 # If answer for current state is already calculated then just return dp[i][j][k] if dp[i][j][k] != -1: return dp[i][j][k] # Answer initialized with big value ans = sys.maxsize # Calling recursive function for taking j'th element of array A[] if j != N: ans = min(ans, solve(i - A[j], j + 1, k, A, B, N) + 1) # Calling recursive function for taking k'th element of array B[] if k != N: ans = min(ans, solve(i - B[k], j, k + 1, A, B, N) + 1) # Save and return dp value dp[i][j][k] = ans return ansdef minOperations(A: List[int], B: List[int], N: int, M: int) -> int: # Minimum operations return solve(M, 0, 0, A, B, N)# Driver codeA = [1, 9, 1, 4, 0, 1]B = [3, 2, 1, 5, 9, 10]N = len(A)M = 12print(minOperations(A, B, N, M))A1 = [0, 1, 2, 3, 5]B1 = [5, 0, 0, 0, 9]N1 = len(A1)M1 = 6print(minOperations(A1, B1, N1, M1))# This code is contributed by lokeshpotta20. |
C#
// C# code to implement the approachusing System;using System.Linq;public class GFG { // dp table initialized with -1 static int[, , ] dp = new int[501, 101, 101]; // Recursive Function to minimize the // operations to collect at least sum of M static int Solve(int i, int j, int k, int[] A, int[] B, int N) { // Base case if (i <= 0) { return 0; } // If answer for current state is // already calculated then just // return dp[i][j][k] if (dp[i, j, k] != -1) { return dp[i, j, k]; } // Answer initialized with zero int ans = (int)1e9; // Calling recursive function for // taking j'th element of array A[] if (j != N) { ans = Math.Min( ans, Solve(i - A[j], j + 1, k, A, B, N) + 1); } // Calling recursive function for // taking k'th element of array B[] if (k != N) { ans = Math.Min( ans, Solve(i - B[k], j, k + 1, A, B, N) + 1); } // Save and return dp value return dp[i, j, k] = ans; } // Function to minimize the operations // to collect at least sum of M static int MinOperations(int[] A, int[] B, int N, int M) { // Filling dp table with - 1 for (int i = 0; i < dp.GetLength(0); i++) { for (int j = 0; j < dp.GetLength(1); j++) { for (int k = 0; k < dp.GetLength(2); k++) { dp[i, j, k] = -1; } } } // Minimum operations int ans = Solve(M, 0, 0, A, B, N); return ans; } static public void Main() { // Code // Input 1 int[] A = { 1, 9, 1, 4, 0, 1 }, B = { 3, 2, 1, 5, 9, 10 }; int N = A.Length; int M = 12; // Function Call Console.WriteLine(MinOperations(A, B, N, M)); // Input 2 int[] A1 = { 0, 1, 2, 3, 5 }, B1 = { 5, 0, 0, 0, 9 }; int N1 = A1.Length; int M1 = 6; // Function Call Console.WriteLine(MinOperations(A1, B1, N1, M1)); }}// This code is contributed by lokeshmvs21. |
Javascript
// dp table initialized with -1let dp = new Array(501);for(let i = 0; i < 501; i++) { dp[i] = new Array(101); for(let j = 0; j < 101; j++) { dp[i][j] = new Array(101).fill(-1); }}// Recursive Function to minimize the// operations to collect at least sum of Mfunction solve(i, j, k, A, B, N) { // Base case if (i <= 0) { return 0; } // If answer for current state is // already calculated then just // return dp[i][j][k] if (dp[i][j][k] !== -1) return dp[i][j][k]; // Answer initialized with zero let ans = 1e9; // Calling recursive function for // taking j'th element of array A[] if (j !== N) ans = Math.min(ans, solve(i - A[j], j + 1, k, A, B, N) + 1); // Calling recursive function for // taking k'th element of array B[] if (k !== N) ans = Math.min(ans, solve(i - B[k], j, k + 1, A, B, N) + 1); // Save and return dp value return dp[i][j][k] = ans;}// Function to minimize the operations// to collect at least sum of Mfunction minOperations(A, B, N, M) { // Minimum operations let ans = solve(M, 0, 0, A, B, N); return ans;}// Input 1let A = [1, 9, 1, 4, 0, 1];let B = [3, 2, 1, 5, 9, 10];let N = A.length;let M = 12;// Function Callconsole.log(minOperations(A, B, N, M));// Input 2let A1 = [0, 1, 2, 3, 5]; let B1 = [5, 0, 0, 0, 9];let N1 = A1.length;let M1 = 6;// Function Callconsole.log(minOperations(A1, B1, N1, M1));// This code is contributed by aadityamaharshi21. |
Output
3 3
Time Complexity: O(N2 * M)
Auxiliary Space: O(N2 * M)
Related Articles:
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!
