Minimize transfer operations to get the given Array sum

0 0 15 minutes read

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-1
vector<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 Operations
void 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 code
int 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 approach
import 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-1
def 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 Operations
def 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 code
if __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 approach
using 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-1
const 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 Operations
const 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 code
let N, M, targetSum = 12;
let A = [1, 2, 1, 4];
let B = [5, 12, 11];
N = A.length;
M = B.length;
 
// Function call
minOperations(N, M, targetSum, A, B);
 
// This code is contributed by rakeshsahni

Output

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-1
vector<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 Operations
void 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 code
int 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 Sonigara
public 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 List
import sys
 
# Function to create dp, where
# dp[j] represents the minimum number of
# elements required to make sum j till i-1
def 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 Operations
def 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 case
if __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-1
function 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 Operations
function 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 case
let 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

Time Complexity: O(N * sum)
Auxiliary Space: O(sum)

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 zambiatek!