ন্যূনতম সংখ্যাগুলির গুণনের সর্বনিম্ন যোগফল


কাঠিন্য মাত্রা কঠিন
প্রায়শই জিজ্ঞাসা করা হয় Accenture কালো শিলা জিই হেলথকেয়ার জেপি মরগান পেপ্যাল
বিন্যাস ডায়নামিক প্রোগ্রামিং

সমস্যাটি "ন্যূনতম সংখ্যাগুলির গুণনের সর্বনিম্ন যোগফল" সূচিত করে যে আপনি এন পূর্ণসংখ্যার এবং আপনাকে একবারে সংলগ্ন দুটি উপাদান নিয়ে এবং একটি সংখ্যার অবশিষ্ট না হওয়া পর্যন্ত তাদের যোগফল 100 ফিরিয়ে রেখে সমস্ত সংখ্যার গুণনের যোগফলকে হ্রাস করতে হবে।

উদাহরণ

ন্যূনতম সংখ্যাগুলির গুণনের সর্বনিম্ন যোগফল

10 20 30
1100

ব্যাখ্যা

প্রথমত, আমরা 10 পেতে 20 এবং 200 কে গুণিত করি (10 + 20)% 100 = 30. এখন আমাদের কাছে [30, 30] রয়েছে। তারপরে 30 * 30 = 900 কে গুণ করুন Thus সুতরাং উত্তরটি 900 + 200 = 1100।

যদি আমরা প্রথমে 20 এবং 30 কে গুণিত করি We আমরা (20 * 30) + (10 * 50) = 1100 পেয়েছি Thus সুতরাং উভয় উপায়েই আমরা একই ফল পেয়েছি।

অভিগমন

সমস্যাটি আমাদের ন্যূনতম যোগফলটি খুঁজতে বলেছে যা আপনি জোড়ায় সংখ্যাগুলি গুণিয়ে রাখেন এবং তারপরে সংযোজন করে যান। সমস্যাটি সমাধান করার জন্য একটি নিখুঁত পদ্ধতির ব্যবহার করা হচ্ছে পুনরাবৃত্তির। সমস্ত ক্রম নির্ধারণ করুন এবং তারপরে বিবেচনা করুন যে এই ক্রমান্বয়ে সূচিগুলি বোঝায় যা জোড়ায় বহুগুণ করা উচিত। তবে এই পদ্ধতিটি সময়সাপেক্ষ, কারণ ক্রমবর্ধনের প্রজন্মের কল্পিত সময় জটিলতা রয়েছে।

এই সময়সাপেক্ষ পদ্ধতির পরিবর্তে আমাদের অন্য যে কোনও সমাধানের কথা চিন্তা করা উচিত যা সময়সীমার অধীনে ফলাফল গণনা করতে সক্ষম। এখন ডায়নামিক প্রোগ্রামিং আমাদের সহায়তা আসে। স্ট্যান্ডার্ড ম্যাট্রিক চেইন গুণটির সমস্যার তুলনায় সমস্যাটি কিছুটা ভিন্ন। এখানে এই সমস্যায় আমরা প্রথমে 2 টি উপাদান, তারপরে 3 টি উপাদান এবং এর জন্য উত্তরগুলি গণনা করি। সুতরাং আমরা সূচকগুলি একটি পুনরাবৃত্ত ফাংশনগুলিতে সংরক্ষণের জন্য দুটি ভেরিয়েবল রাখি যা ক্রমের সীমা চিহ্নিত করে। তারপরে আমরা ক্রমটি 2 ভাগে বিভক্ত করেছি। এবং তারপরে এই দুটি সাব-প্রবলেমগুলি সমাধান করুন। আমরা বেস কেসে আঘাত না করা পর্যন্ত এই প্রক্রিয়াটি চলতে থাকবে। উভয় সূচক একই হয় যখন এখানে বেস কেস হয়। তারপরে আমরা যেমন এই সাব-প্রবলেমের উত্তর গণনা করেছি আমরা প্রাথমিক সমস্যার ফলাফল পেতে উত্তরগুলি একত্রিত করি।

কোড

নম্বরের ন্যূনতম যোগফলের জন্য সি ++ কোড

#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

জাভা কোড n সংখ্যার নূন্যতম যোগফল খুঁজতে

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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন ^ 3), কারণ সেখানে N ^ 2 টি রাজ্য রয়েছে এবং প্রত্যেকের জন্য ফলাফল গণনা করতে আমরা আনুমানিক N সংখ্যক রাজ্যের উপর নির্ভরশীল। সুতরাং সময় জটিলতা বহুপদী।

স্পেস জটিলতা ity

ও (এন ^ 2), কারণ আমরা একটি 2D ডিপি টেবিল তৈরি করেছি। সুতরাং স্থান জটিলতাও বহুপদী।