Minimum total sum from the given two arrays

0 2 8 minutes read

Given two arrays A[] and B[] of N positive integers and a cost C. We can choose any one element from each index of the given arrays i.e., for any index i we can choose only element A[i] or B[i]. The task is to find the minimum total sum of selecting N elements from the given two arrays and if we are selecting any element from A[] to B[] or vice-versa in the next iteration then the cost C is also added to the sum.

Note: Choose element in increasing order of index i.e., 0 ? i < N.

Examples:

Input: N = 9, A[] = {7, 6, 18, 6, 16, 18, 1, 17, 17}, B[] = {6, 9, 3, 10, 9, 1, 10, 1, 5}, C = 2
Output: 49
Explanation:
On taking the 1st element from array A, sum = 7
On taking the 2nd element from array A, sum = 7 + 6 = 13
On taking the 3rd element from array B, as we are entering from array A to array B, sum = 13 + 3 + 2 = 18
On taking the 4th element from array A, as we are entering from array B to array A, sum = 18 + 6 + 2 = 26
On taking the 5th element from array B, as we are entering from array A to array B, sum = 26 + 9 + 2 = 37
On taking the 6th element form array B, sum = 37 + 1 = 38
On taking the 7th element from array A, as we are entering from array B to array A, sum = 38 + 1 + 2 = 41
On taking the 8th element form array B, as we are entering from array A to array B, sum = 41 + 1 + 2 = 44
On taking the 9th element from array B, sum = 44 + 5 = 49.

Input: N = 9, A = {3, 2, 3, 1, 3, 3, 1, 4, 1}, B = {1, 2, 3, 4, 4, 1, 2, 1, 3}, C = 1
Output: 18
Explanation:
On taking the 1st element from array B, sum = 1
On taking the 2nd element from array A, sum = 1 + 2 = 3
On taking the 3rd element from array A, sum = 3 + 3 = 6
On taking the 4th element from array A, sum = 6 + 1 = 7
On taking the 5th element from array A, sum = 7 + 3 = 10
On taking the 6th element form array B, as we are entering from array A to array B, sum = 10 + 1 + 1 = 12
On taking the 7th element from array A, as we are entering from array B to array A, sum = 12 + 1 + 1 = 14
On taking the 8th element form array B, as we are entering from array A to array B, sum = 14 + 1 + 1 = 16
On taking the 9th element from array A, as we are entering from array B to array A, sum = 16 + 1 + 1 = 18.

Approach: We will use Dynamic Programming to solve this problem. Below are the steps:

Create a 2D array dp[][] of N rows and two columns and initialize all elements of dp to infinity.
There can be 4 possible cases of adding the elements from both the arrays:
- Adding an element from array a[] when the previously added element is from array a[].
- Adding an element from array a[] when the previously added element is from array b[]. In this case there is a penalty of adding the integer C with the result.
- Adding an element from array b[] when the previously added element is from array b[].
- Adding an element from array b[] when the previously added element is from array a[]. In this case there is a penalty of adding the integer C with the result.
Update the dp array each time with the minimum value of the above four conditions.
The minimum of dp[n-1][0] and dp[n-1][1] is the total minimum sum of selecting N elements.

Below is the implementation of the above approach:

C++

// C++ program for the above approach 
#include <bits/stdc++.h> 
using namespace std; 
 
// Function that prints minimum sum 
// after selecting N elements 
void minimumSum(int a[], int b[], 
                int c, int n) 
{ 
 
    // Initialise the dp array 
    vector<vector<int> > dp(n, 
                            vector<int>(2, 
                                        1e6)); 
 
    // Base Case 
    dp[0][0] = a[0]; 
    dp[0][1] = b[0]; 
 
    for (int i = 1; i < n; i++) { 
 
        // Adding the element of array a if 
        // previous element is also from array a 
        dp[i][0] = min(dp[i][0], 
                    dp[i - 1][0] + a[i]); 
 
        // Adding the element of array a if 
        // previous element is from array b 
        dp[i][0] = min(dp[i][0], 
                    dp[i - 1][1] + a[i] + c); 
 
        // Adding the element of array b if 
        // previous element is from array a 
        // with an extra penalty of integer C 
        dp[i][1] = min(dp[i][1], 
                    dp[i - 1][0] + b[i] + c); 
 
        // Adding the element of array b if 
        // previous element is also from array b 
        dp[i][1] = min(dp[i][1], 
                    dp[i - 1][1] + b[i]); 
    } 
 
    // Print the minimum sum 
    cout << min(dp[n - 1][0], 
                dp[n - 1][1]) 
        << "\n"; 
} 
 
// Driver Code 
int main() 
{ 
    // Given array arr1[] and arr2[] 
    int arr1[] = { 7, 6, 18, 6, 16, 
                18, 1, 17, 17 }; 
 
    int arr2[] = { 6, 9, 3, 10, 9, 
                1, 10, 1, 5 }; 
 
    // Given cost 
    int C = 2; 
 
    int N = sizeof(arr1) / sizeof(arr1[0]); 
 
    // Function Call 
    minimumSum(arr1, arr2, C, N); 
 
    return 0; 
} 

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function that prints minimum sum
// after selecting N elements
static void minimumSum(int a[], int b[],
                       int c, int n)
{
     
    // Initialise the dp array
    int [][]dp = new int[n][2];
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            dp[i][j] = (int) 1e6;
        }
    }
     
    // Base Case
    dp[0][0] = a[0];
    dp[0][1] = b[0];
 
    for(int i = 1; i < n; i++) 
    {
         
        // Adding the element of array a if
        // previous element is also from array a
        dp[i][0] = Math.min(dp[i][0],
                            dp[i - 1][0] + a[i]);
 
        // Adding the element of array a if
        // previous element is from array b
        dp[i][0] = Math.min(dp[i][0],
                            dp[i - 1][1] + a[i] + c);
 
        // Adding the element of array b if
        // previous element is from array a
        // with an extra penalty of integer C
        dp[i][1] = Math.min(dp[i][1],
                            dp[i - 1][0] + b[i] + c);
 
        // Adding the element of array b if
        // previous element is also from array b
        dp[i][1] = Math.min(dp[i][1],
                            dp[i - 1][1] + b[i]);
    }
 
    // Print the minimum sum
    System.out.print(Math.min(dp[n - 1][0],
                              dp[n - 1][1]) + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array arr1[] and arr2[]
    int arr1[] = { 7, 6, 18, 6, 16,
                   18, 1, 17, 17 };
 
    int arr2[] = { 6, 9, 3, 10, 9,
                   1, 10, 1, 5 };
 
    // Given cost
    int C = 2;
 
    int N = arr1.length;
 
    // Function call
    minimumSum(arr1, arr2, C, N);
}
}
 
// This code is contributed by gauravrajput1

Python3

# Python3 program for the above approach 
 
# Function that prints minimum sum 
# after selecting N elements 
def minimumSum(a, b, c, n): 
     
    # Initialise the dp array 
    dp = [[1e6 for i in range(2)] 
            for j in range(n)] 
 
    # Base Case 
    dp[0][0] = a[0] 
    dp[0][1] = b[0] 
 
    for i in range(1, n): 
 
        # Adding the element of array a if 
        # previous element is also from array a 
        dp[i][0] = min(dp[i][0], 
                    dp[i - 1][0] + a[i]) 
 
        # Adding the element of array a if 
        # previous element is from array b 
        dp[i][0] = min(dp[i][0], 
                    dp[i - 1][1] + a[i] + c) 
 
        # Adding the element of array b if 
        # previous element is from array a 
        # with an extra penalty of integer C 
        dp[i][1] = min(dp[i][1], 
                    dp[i - 1][0] + b[i] + c) 
 
        # Adding the element of array b if 
        # previous element is also from array b 
        dp[i][1] = min(dp[i][1], 
                    dp[i - 1][1] + b[i]) 
 
    # Print the minimum sum 
    print(min(dp[n - 1][0], dp[n - 1][1])) 
 
# Driver code 
if __name__ == '__main__': 
 
    # Given array arr[] 
    arr1 = [ 7, 6, 18, 6, 16, 
            18, 1, 17, 17 ] 
 
    arr2 = [ 6, 9, 3, 10, 9, 
            1, 10, 1, 5 ] 
 
    # Given cost 
    C = 2
 
    N = len(arr1) 
 
    # Function Call 
    minimumSum(arr1, arr2, C, N) 
 
# This code is contributed by Shivam Singh 

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function that prints minimum sum
// after selecting N elements
static void minimumSum(int []a, int []b,
                       int c, int n)
{
     
    // Initialise the dp array
    int [,]dp = new int[n, 2];
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            dp[i, j] = (int)1e6;
        }
    }
     
    // Base Case
    dp[0, 0] = a[0];
    dp[0, 1] = b[0];
 
    for(int i = 1; i < n; i++) 
    {
         
        // Adding the element of array a if
        // previous element is also from array a
        dp[i, 0] = Math.Min(dp[i, 0],
                            dp[i - 1, 0] + a[i]);
 
        // Adding the element of array a if
        // previous element is from array b
        dp[i, 0] = Math.Min(dp[i, 0],
                            dp[i - 1, 1] + a[i] + c);
 
        // Adding the element of array b if
        // previous element is from array a
        // with an extra penalty of integer C
        dp[i, 1] = Math.Min(dp[i, 1],
                            dp[i - 1, 0] + b[i] + c);
 
        // Adding the element of array b if
        // previous element is also from array b
        dp[i, 1] = Math.Min(dp[i, 1],
                            dp[i - 1, 1] + b[i]);
    }
 
    // Print the minimum sum
    Console.Write(Math.Min(dp[n - 1, 0],
                           dp[n - 1, 1]) + "\n");
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array arr1[] and arr2[]
    int []arr1 = { 7, 6, 18, 6, 16,
                   18, 1, 17, 17 };
 
    int []arr2 = { 6, 9, 3, 10, 9,
                   1, 10, 1, 5 };
 
    // Given cost
    int C = 2;
 
    int N = arr1.Length;
 
    // Function call
    minimumSum(arr1, arr2, C, N);
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function that prints minimum sum
// after selecting N elements
function minimumSum(a, b, c, n)
{
     
    // Initialise the dp array
    let dp =  new Array(n);
    for (var i = 0; i < dp.length; i++) {
    dp[i] = new Array(2);
    }
 
    for(let i = 0; i < n; i++)
    {
        for(let j = 0; j < 2; j++)
        {
            dp[i][j] = 1e6;
        }
    }
     
    // Base Case
    dp[0][0] = a[0];
    dp[0][1] = b[0];
 
    for(let i = 1; i < n; i++) 
    {
         
        // Adding the element of array a if
        // previous element is also from array a
        dp[i][0] = Math.min(dp[i][0],
                            dp[i - 1][0] + a[i]);
 
        // Adding the element of array a if
        // previous element is from array b
        dp[i][0] = Math.min(dp[i][0],
                            dp[i - 1][1] + a[i] + c);
 
        // Adding the element of array b if
        // previous element is from array a
        // with an extra penalty of integer C
        dp[i][1] = Math.min(dp[i][1],
                            dp[i - 1][0] + b[i] + c);
 
        // Adding the element of array b if
        // previous element is also from array b
        dp[i][1] = Math.min(dp[i][1],
                            dp[i - 1][1] + b[i]);
    }
 
    // Print the minimum sum
    document.write(Math.min(dp[n - 1][0],
                              dp[n - 1][1]) + "<br/>");
}
 
// Driver Code
 
    // Given array arr1[] and arr2[]
    let arr1 = [ 7, 6, 18, 6, 16,
                   18, 1, 17, 17 ];
 
    let arr2 = [ 6, 9, 3, 10, 9,
                   1, 10, 1, 5 ];
 
    // Given cost
    let C = 2;
 
    let N = arr1.length;
 
    // Function call
    minimumSum(arr1, arr2, C, N);
 
</script>

Output:

Time Complexity: O(N), where N is the size of the given array.
Auxiliary Space: O(N), for creating additional dp array.

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!