Given two integer arrays A[] and B[] of length N and M respectively, the task is to find the minimum number of operations required such that the sum of elements in array A becomes targetSum. In one operation you can transfer an element from A[] to B[] or from B[] to A[].
Examples
Input: N = 4, M = 3, targetSum = 12, A[] = {1, 2, 1, 4}, B[] = {5, 12, 11}
Output: 2
Explanation: We can do the following two operations
1) Transfer 1 from A[] to B[]
2) Transfer 5 from B[] to A[]
So, the array becomes 5 + 2 + 1 + 4 = 12, which is equal to the target sum.Input: N = 4, M = 5, targetSum = 12, A[] = {7, 2, 4, 3], B[] = {8, 1, 1, 7, 9}
Output: 1
Explanation: We can do the following two operations
1) Transfer 4 from A[] to B[]
So, the array becomes 7 + 2 + 3 = 12, which is equal to the target sum.
Approach: Implement the idea below to solve the problem:
We can reduce this problem into subproblems. Let’s say elements with sum p are transferred from array A[] to array B[] and elements with sum q are transferred from array B[] to array A[]. So, the number of operations will be minimum when we take minimum number of elements from array A[] with sum p and minimum number of elements from array B[] with sum q.
This Problem can be solved by using Dynamic Programming, where we have to find minimum number of elements in an array with a given sum.
Follow the below steps to implement the idea:
- Create two dynamic arrays (say dp1[][] and dp2[][]).
- Let dp1[i][j] represent the minimum number of elements required in array A to make sum j till index i – 1, similarly, dp2[i][j] can also be defined for array B[] in the same way.
- We can create dp1[][] and dp2[][] using this transformation dp[i][j] = min(dp[i – 1][j], dp[i – 1][j – a[i – 1]] + 1).
- The final value of array A[] will be targetSum, let p be the sum removed from array A[] and q be the sum removed from array B[](added to array A). Then the total number of operations will be dp1[N][p]+dp2[M][q].
- Iterate from p = 0 to p = sum1 (where sum1 is the initial sum of values of array A). We know that targetSum = sum1 – p + q, then q will be targetSum – sum1 + p.
- Answer will be minimum of all dp1[N][p] + dp2[M][q] from p = 0 to p = sum1.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to create dp1 and dp2, where// dp[i][j] representsminimum number of// elements required to make sum j till i-1vector<vector<int> > minSizeSum(int a[], int n){ // Calculating initial sum of array int sum = 0; for (int i = 0; i < n; i++) sum += a[i]; // Initialising dp with 1e9 vector<vector<int> > dp(n + 1, vector<int>(sum + 1, 1e9)); // 0 elements are needed to make sum 0 for (int i = 0; i <= n; i++) dp[i][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= sum; j++) { // If current element is not // selected number of elements will // be dp[i-1][j] and If current // element is selected number of // elements will be dp[i-1][j-a[i-1]]+1 if (j < a[i - 1]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - a[i - 1]] + 1); } } return dp;}// Function to calculate Minimum Operationsvoid minOperations(int N, int M, int targetSum, int A[], int B[]){ // Form Dp vector<vector<int> > dp1 = minSizeSum(A, N), dp2 = minSizeSum(B, M); int sum1 = 0, sum2 = 0; // Calculating sum of elements of both arrays for (int i = 0; i < N; i++) sum1 += A[i]; for (int i = 0; i < M; i++) sum2 += B[i]; int ans = 1e9; for (int p = 0; p <= sum1; p++) { // targetSum = sum1-p+q // We calculate q from p int q = targetSum - sum1 + p; if (q < 0 || q > sum2) continue; // Number of operations ans = min(ans, dp1[N][p] + dp2[M][q]); } if (ans == 1e9) ans = -1; // Print Minimum operation Required cout << ans << endl;}// Driver codeint main(){ int N, M, targetSum = 12; int A[] = { 1, 2, 1, 4 }; int B[] = { 5, 12, 11 }; N = sizeof(A) / sizeof(A[0]); M = sizeof(B) / sizeof(B[0]); // Function call minOperations(N, M, targetSum, A, B); return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to create dp1 and dp2, where // dp[i][j] representsminimum number of // elements required to make sum j till i-1 static int[][] minSizeSum(int[] a, int n) { // Calculating initial sum of array int sum = 0; for (int i = 0; i < n; i++) { sum += a[i]; } // Initialising dp with 1e9 int[][] dp = new int[n + 1][sum + 1]; for (int i = 0; i < n + 1; i++) { for (int j = 0; j < sum + 1; j++) { dp[i][j] = (int)1e9; } } // 0 elements are needed to make sum 0 for (int i = 0; i <= n; i++) { dp[i][0] = 0; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= sum; j++) { // If current element is not // selected number of elements will // be dp[i-1][j] and If current // element is selected number of // elements will be dp[i-1][j-a[i-1]]+1 if (j < a[i - 1]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = Math.min( dp[i - 1][j], dp[i - 1][j - a[i - 1]] + 1); } } } return dp; } // Function to calculate Minimum Operations static void minOperations(int N, int M, int targetSum, int[] A, int[] B) { // Form Dp int[][] dp1 = minSizeSum(A, N); int[][] dp2 = minSizeSum(B, M); int sum1 = 0, sum2 = 0; // Calculating sum of elements of both arrays for (int i = 0; i < N; i++) { sum1 += A[i]; } for (int i = 0; i < M; i++) { sum2 += B[i]; } int ans = (int)1e9; for (int p = 0; p <= sum1; p++) { // targetSum = sum1-p+q // We calculate q from p int q = targetSum - sum1 + p; if (q < 0 || q > sum2) { continue; } // Number of operations ans = Math.min(ans, dp1[N][p] + dp2[M][q]); } if (ans == (int)1e9) { ans = -1; } // Print Minimum operation Required System.out.println(ans); } public static void main(String[] args) { int targetSum = 12; int[] A = { 1, 2, 1, 4 }; int[] B = { 5, 12, 11 }; int N = A.length; int M = B.length; // Function call minOperations(N, M, targetSum, A, B); }}// This code is contributed by lokeshmvs21. |
Python3
# Python code to implement the approach# Function to create dp1 and dp2, where# dp[i][j] representsminimum number of# elements required to make sum j till i-1def minSizeSum(a, n): # Calculating initial sum of array sum = 0 for i in range(n): sum += a[i] # Initialising dp with 1e9 dp = [[1e9 for i in range(sum + 1)] for j in range(n + 1)] # 0 elements are needed to make sum 0 for i in range(n + 1): dp[i][0] = 0 for i in range(1, n + 1): for j in range(1, sum + 1): # If current element is not # selected number of elements will # be dp[i-1][j] and If current # element is selected number of # elements will be dp[i-1][j-a[i-1]]+1 if (j < a[i - 1]): dp[i][j] = dp[i - 1][j] else: dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - a[i - 1]] + 1) return dp# Function to calculate Minimum Operationsdef minOperations(N, M, targetSum, A, B): # Form Dp dp1 = minSizeSum(A, N) dp2 = minSizeSum(B, M) sum1 = 0 sum2 = 0 # Calculating sum of elements of both arrays for i in range(N): sum1 += A[i] for i in range(M): sum2 += B[i] ans = 1e9 for p in range(sum1 + 1): # targetSum = sum1-p+q # We calculate q from p q = targetSum - sum1 + p if (q < 0 or q > sum2): continue # Number of operations ans = min(ans, dp1[N][p] + dp2[M][q]) if (ans == 1e9): ans = -1 # Print Minimum operation Required print(ans)# Driver codeif __name__ == '__main__': targetSum = 12 A = [1, 2, 1, 4] B = [5, 12, 11] N = len(A) M = len(B) # Function call minOperations(N, M, targetSum, A, B)# This code is contributed by Tapesh(tapeshdua420) |
C#
// C# code to implement the approachusing System;class GFG { // Function to create dp1 and dp2, where // dp[i][j] representsminimum number of // elements required to make sum j till i-1 static int[, ] minSizeSum(int[] a, int n) { // Calculating initial sum of array int sum = 0; for (int i = 0; i < n; i++) { sum += a[i]; } // Initialising dp with 1e9 int[, ] dp = new int[n + 1, sum + 1]; for (int i = 0; i < n + 1; i++) { for (int j = 0; j < sum + 1; j++) { dp[i, j] = (int)1e9; } } // 0 elements are needed to make sum 0 for (int i = 0; i <= n; i++) { dp[i, 0] = 0; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= sum; j++) { // If current element is not // selected number of elements will // be dp[i-1][j] and If current // element is selected number of // elements will be dp[i-1][j-a[i-1]]+1 if (j < a[i - 1]) { dp[i, j] = dp[i - 1, j]; } else { dp[i, j] = Math.Min( dp[i - 1, j], dp[i - 1, j - a[i - 1]] + 1); } } } return dp; } // Function to calculate Minimum Operations static void minOperations(int N, int M, int targetSum, int[] A, int[] B) { // Form Dp int[, ] dp1 = minSizeSum(A, N); int[, ] dp2 = minSizeSum(B, M); int sum1 = 0, sum2 = 0; // Calculating sum of elements of both arrays for (int i = 0; i < N; i++) { sum1 += A[i]; } for (int i = 0; i < M; i++) { sum2 += B[i]; } int ans = (int)1e9; for (int p = 0; p <= sum1; p++) { // targetSum = sum1-p+q // We calculate q from p int q = targetSum - sum1 + p; if (q < 0 || q > sum2) { continue; } // Number of operations ans = Math.Min(ans, dp1[N, p] + dp2[M, q]); } if (ans == (int)1e9) { ans = -1; } // Print Minimum operation Required Console.WriteLine(ans); } public static void Main() { int targetSum = 12; int[] A = { 1, 2, 1, 4 }; int[] B = { 5, 12, 11 }; int N = A.Length; int M = B.Length; // Function call minOperations(N, M, targetSum, A, B); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
// JavaScript code to implement the approach// Function to create dp1 and dp2, where// dp[i][j] representsminimum number of// elements required to make sum j till i-1const minSizeSum = (a, n) => { // Calculating initial sum of array let sum = 0; for (let i = 0; i < n; i++) sum += a[i]; // Initialising dp with 1e9 let dp = new Array(n + 1).fill(1e9).map(() => new Array(sum + 1).fill(1e9)); // 0 elements are needed to make sum 0 for (let i = 0; i <= n; i++) dp[i][0] = 0; for (let i = 1; i <= n; i++) { for (let j = 1; j <= sum; j++) { // If current element is not // selected number of elements will // be dp[i-1][j] and If current // element is selected number of // elements will be dp[i-1][j-a[i-1]]+1 if (j < a[i - 1]) dp[i][j] = dp[i - 1][j]; else dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - a[i - 1]] + 1); } } return dp;}// Function to calculate Minimum Operationsconst minOperations = (N, M, targetSum, A, B) => { // Form Dp let dp1 = minSizeSum(A, N), dp2 = minSizeSum(B, M); let sum1 = 0, sum2 = 0; // Calculating sum of elements of both arrays for (let i = 0; i < N; i++) sum1 += A[i]; for (let i = 0; i < M; i++) sum2 += B[i]; let ans = 1e9; for (let p = 0; p <= sum1; p++) { // targetSum = sum1-p+q // We calculate q from p let q = targetSum - sum1 + p; if (q < 0 || q > sum2) continue; // Number of operations ans = Math.min(ans, dp1[N][p] + dp2[M][q]); } if (ans == 1e9) ans = -1; // Print Minimum operation Required console.log(`${ans}<br/>`);}// Driver codelet N, M, targetSum = 12;let A = [1, 2, 1, 4];let B = [5, 12, 11];N = A.length;M = B.length;// Function callminOperations(N, M, targetSum, A, B);// This code is contributed by rakeshsahni |
Output
2
Time Complexity: O(N * sum)
Auxiliary Space: O(N * sum)
Efficient approach : Space optimization
In previous approach the current value dp[i][j] is only depend upon the current and previous row values of DP. So to optimize the space complexity we use a single 1D array to store the computations.
Implementation steps:
- Create a 1D vector dp of size sum+1.
- Set a base case by initializing the values of DP.
- Now iterate over subproblems by the help of nested loop and get the current value from previous computations.
- Initialize a variable ans to store the final answer and update it by iterating through the Dp.
- At last return and print the final answer stored in ans if exists else return -1.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;// Function to create dp, where// dp[j] represents the minimum number of// elements required to make sum j till i-1vector<int> minSizeSum(int a[], int n){ int sum = 0; for (int i = 0; i < n; i++) sum += a[i]; vector<int> dp(sum + 1, 1e9); dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = sum; j >= a[i]; j--) { dp[j] = min(dp[j], dp[j - a[i]] + 1); } } return dp;}// Function to calculate Minimum Operationsvoid minOperations(int N, int M, int targetSum, int A[], int B[]){ // Form Dp int sum_a = accumulate(A, A + N, 0); int sum_b = accumulate(B, B + M, 0); vector<int> dp1 = minSizeSum(A, N), dp2 = minSizeSum(B, M); int ans = 1e9; for (int p = 0; p <= sum_a; p++) { int q = targetSum - sum_a + p; if (q < 0 || q > sum_b) { continue; } // Number of operations ans = min(ans, dp1[p] + dp2[q]); } if (ans == 1e9) ans = -1; cout << ans << endl;}// Driver codeint main(){ int N, M, targetSum = 12; int A[] = { 1, 2, 1, 4 }; int B[] = { 5, 12, 11 }; N = sizeof(A) / sizeof(A[0]); M = sizeof(B) / sizeof(B[0]); // Function call minOperations(N, M, targetSum, A, B); return 0;} |
Java
import java.util.Arrays;// Nikunj Sonigarapublic class GFG { static int[] minSizeSum(int[] a) { int sum = 0; for (int num : a) sum += num; int[] dp = new int[sum + 1]; Arrays.fill(dp, 1000000000); dp[0] = 0; for (int num : a) { for (int j = sum; j >= num; j--) { dp[j] = Math.min(dp[j], dp[j - num] + 1); } } return dp; } static void minOperations(int N, int M, int targetSum, int[] A, int[] B) { int sum_a = Arrays.stream(A).sum(); int sum_b = Arrays.stream(B).sum(); int[] dp1 = minSizeSum(A); int[] dp2 = minSizeSum(B); int ans = 1000000000; for (int p = 0; p <= sum_a; p++) { int q = targetSum - sum_a + p; if (q < 0 || q > sum_b) { continue; } ans = Math.min(ans, dp1[p] + dp2[q]); } if (ans == 1000000000) ans = -1; System.out.println(ans); } public static void main(String[] args) { int N, M, targetSum = 12; int[] A = { 1, 2, 1, 4 }; int[] B = { 5, 12, 11 }; N = A.length; M = B.length; minOperations(N, M, targetSum, A, B); }} |
Python3
from typing import Listimport sys# Function to create dp, where# dp[j] represents the minimum number of# elements required to make sum j till i-1def minSizeSum(a: List[int]) -> List[int]: n = len(a) _sum = sum(a) dp = [sys.maxsize] * (_sum + 1) dp[0] = 0 for i in range(n): for j in range(_sum, a[i] - 1, -1): dp[j] = min(dp[j], dp[j - a[i]] + 1) return dp # Function to calculate Minimum Operationsdef minOperations(N: int, M: int, targetSum: int, A: List[int], B: List[int]) -> None: # Form Dp sum_a = sum(A) sum_b = sum(B) dp1 = minSizeSum(A) dp2 = minSizeSum(B) ans = sys.maxsize for p in range(sum_a + 1): q = targetSum - sum_a + p if q < 0 or q > sum_b: continue # Number of operations ans = min(ans, dp1[p] + dp2[q]) if ans == sys.maxsize: ans = -1 print(ans)# test caseif __name__ == "__main__": targetSum = 12 A = [1, 2, 1, 4] B = [5, 12, 11] N = len(A) M = len(B) minOperations(N, M, targetSum, A, B) |
C#
using System;using System.Linq;using System.Collections.Generic;class GFG{ // Function to create dp, where dp[j] represents the minimum number of // elements required to make sum j till i-1 static List<int> MinSizeSum(int[] a, int n) { int sum = a.Sum(); List<int> dp = new List<int>(new int[sum + 1]); for (int i = 1; i <= sum; i++) { dp[i] = 1000000009; } dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = sum; j >= a[i]; j--) { dp[j] = Math.Min(dp[j], dp[j - a[i]] + 1); } } return dp; } // Function to calculate Minimum Operations static void MinOperations(int N, int M, int targetSum, int[] A, int[] B) { // Form Dp int sum_a = A.Sum(); int sum_b = B.Sum(); List<int> dp1 = MinSizeSum(A, N); List<int> dp2 = MinSizeSum(B, M); int ans = 1000000009; for (int p = 0; p <= sum_a; p++) { int q = targetSum - sum_a + p; if (q < 0 || q > sum_b) { continue; } // Number of operations ans = Math.Min(ans, dp1[p] + dp2[q]); } if (ans == 1000000009) { ans = -1; } Console.WriteLine(ans); } // Driver code static void Main(string[] args) { int N, M, targetSum = 12; int[] A = { 1, 2, 1, 4 }; int[] B = { 5, 12, 11 }; N = A.Length; M = B.Length; // Function call MinOperations(N, M, targetSum, A, B); }} |
Javascript
// Function to create dp, where// dp[j] represents the minimum number of// elements required to make sum j till i-1function minSizeSum(a, n) { let sum = 0; for (let i = 0; i < n; i++) { sum += a[i]; } let dp = new Array(sum + 1).fill(1e9); dp[0] = 0; for (let i = 0; i < n; i++) { for (let j = sum; j >= a[i]; j--) { dp[j] = Math.min(dp[j], dp[j - a[i]] + 1); } } return dp;}// Function to calculate Minimum Operationsfunction minOperations(N, M, targetSum, A, B) { // Form Dp let sum_a = A.reduce((acc, curr) => acc + curr, 0); let sum_b = B.reduce((acc, curr) => acc + curr, 0); let dp1 = minSizeSum(A, N); let dp2 = minSizeSum(B, M); let ans = 1e9; for (let p = 0; p <= sum_a; p++) { let q = targetSum - sum_a + p; if (q < 0 || q > sum_b) { continue; } // Number of operations ans = Math.min(ans, dp1[p] + dp2[q]); } if (ans == 1e9) { ans = -1; } console.log(ans);}// Test caselet N, M, targetSum = 12;let A = [1, 2, 1, 4];let B = [5, 12, 11];N = A.length;M = B.length;minOperations(N, M, targetSum, A, B); |
Output
2
Time Complexity: O(N * sum)
Auxiliary Space: O(sum)
Related Articles:
- Introduction to Arrays – Data Structures and Algorithms Tutorials
- Introduction to Dynamic Programming – Data Structures and Algorithms Tutorials
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!
