Minimum sum of multiplications of n numbers

Difficulty Level Hard
Frequently asked in Accenture BlackRock GE Healthcare JP Morgan PayPal
Array Dynamic ProgrammingViews 2212

The problem “Minimum sum of multiplications of n numbers” states that you are given n integers and you need to minimize the sum of multiplication of all the numbers by taking two elements that are adjacent at a time and putting back their sum mod 100 until a single number is left.

Example

Minimum sum of multiplications of n numbers

10 20 30
1100

Explanation

First, we multiply 10 and 20 to get 200 then put back (10+20)%100 = 30. Now we have [30, 30]. Then multiply 30*30 = 900. Thus the answer is 900+200 = 1100.

If we would have first multiplied 20 and 30. We would have gotten (20*30) + (10*50)  = 1100. Thus both ways we would have gotten the same result.

Approach

The problem asks us to find the minimum sum that can be found such that you keep on multiplying the numbers in pairs and then doing their addition. A naive approach to solve the problem is using recursion. Generate all the permutations and then consider that these permutations denote the indices which should be multiplied in pairs. But this approach is time-consuming because the generation of permutations has factorial time complexity.

Instead of this time-consuming approach, we should think of any other solution that is able to compute the result under the time limit. Now Dynamic Programming comes to our aid. The problem is a slight variation over the standard Matric Chain Multiplication problem. Here in this problem we first compute the answer for 2 elements, then 3 elements, and so on. So we keep two variables for storing the indices in a recursive function which denote the boundary of the sequence. Then afterward we divided the sequence into 2 parts. And then solve these two subproblems. This process keeps on going until we hit the base case. Here the base case is when both the indices are the same. Then as we have calculated the answer for these subproblems we combine answers to get the result for the initial problem.

Code

C++ code to find Minimum sum of multiplications of n numbers

#include <bits/stdc++.h>
using namespace std;
int dp[5][5];
int sum(int i, int j, int a[]){
  int ans = 0;
  for (int k=i;k<=j;k++)
    ans=(ans+a[k])%100;
  return ans;
}

int minimumSum(int i, int j, int a[]){
    if(i==j)return 0;
  if (dp[i][j] != INT_MAX)
    return dp[i][j];
    // divide the problem into subproblems
  for(int k=i;k<j;k++)
        dp[i][j] = min(dp[i][j], minimumSum(i,k,a)+minimumSum(k+1,j,a) + sum(i,k,a)*sum(k+1,j,a));
  return dp[i][j];
}

int main() {
  int a[] = {10, 20, 30};
  int n = sizeof(a) / sizeof(a[0]);
  for(int i=0;i<5;i++){
        for(int j=0;j<5;j++)
            dp[i][j] = INT_MAX;
  }
  cout<<minimumSum(0,n-1,a);
}

1100

Java code to find Minimum sum of multiplications of n numbers

import java.util.*;
class Main{
  static int dp[][] = new int[5][5];
  static int sum(int i, int j, int a[]){
    int ans = 0;
    for (int k=i;k<=j;k++)
      ans=(ans+a[k])%100;
    return ans;
  }

  static int minimumSum(int i, int j, int a[]){
      if(i==j)return 0;
    if (dp[i][j] != Integer.MAX_VALUE)
      return dp[i][j];
      // divide the problem into subproblems
    for(int k=i;k<j;k++)
          dp[i][j] = Math.min(dp[i][j], minimumSum(i,k,a)+minimumSum(k+1,j,a) + sum(i,k,a)*sum(k+1,j,a));
    return dp[i][j];
  }

  public static void main(String[] args)
  {
    int a[] = {10, 20, 30};
    int n = a.length;
    for(int i=0;i<5;i++){
          for(int j=0;j<5;j++)
              dp[i][j] = Integer.MAX_VALUE;
    }
    int ans = minimumSum(0,n-1,a);
    	System.out.print(ans);
  	}
}
1100

Complexity Analysis

Time Complexity

O(N^3), because there are N^2 states and to compute the result for each we are dependent on an approximate N number of states. Thus the time complexity is polynomial.

Space Complexity

O(N^2), because we have created a 2D DP table. Thus the space complexity is also polynomial.

Translate »