N సంఖ్యల గుణకారాల కనీస మొత్తం


కఠినత స్థాయి హార్డ్
తరచుగా అడుగుతుంది యాక్సెంచర్ నలుపు రాయి GE హెల్త్ జెపి మోర్గాన్ పేపాల్
అర్రే డైనమిక్ ప్రోగ్రామింగ్

“N సంఖ్యల గుణకారాల కనీస మొత్తం” సమస్య మీకు n ఇవ్వబడిందని పేర్కొంది పూర్ణాంకాల మరియు మీరు ఒకేసారి ప్రక్కనే ఉన్న రెండు మూలకాలను తీసుకొని ఒకే సంఖ్య మిగిలిపోయే వరకు వాటి మొత్తం మోడ్ 100 ను తిరిగి ఉంచడం ద్వారా అన్ని సంఖ్యల గుణకారం మొత్తాన్ని తగ్గించాలి.

ఉదాహరణ

N సంఖ్యల గుణకారాల కనీస మొత్తం

10 20 30
1100

వివరణ

మొదట, 10 ను పొందడానికి 20 మరియు 200 లను గుణించి, తిరిగి ఉంచండి (10 + 20)% 100 = 30. ఇప్పుడు మనకు [30, 30] ఉన్నాయి. అప్పుడు 30 * 30 = 900 గుణించాలి. అందువలన సమాధానం 900 + 200 = 1100.

మనం మొదట 20 మరియు 30 గుణించి ఉంటే. (20 * 30) + (10 * 50) = 1100 సంపాదించి ఉండేది. ఈ విధంగా రెండు మార్గాల్లోనూ మేము ఒకే ఫలితాన్ని పొందాము.

అప్రోచ్

మీరు కనుగొనగలిగే కనీస మొత్తాన్ని కనుగొనమని సమస్య మమ్మల్ని అడుగుతుంది, మీరు సంఖ్యలను జంటగా గుణించడం మరియు వాటి అదనంగా చేయడం కొనసాగించండి. సమస్యను పరిష్కరించడానికి ఒక అమాయక విధానం ఉపయోగిస్తోంది సూత్రం. అన్ని ప్రస్తారణలను ఉత్పత్తి చేసి, ఆపై ఈ ప్రస్తారణలు జతలుగా గుణించాల్సిన సూచికలను సూచిస్తాయని పరిగణించండి. కానీ ఈ విధానం సమయం తీసుకుంటుంది ఎందుకంటే ప్రస్తారణల తరం కారకమైన సమయ సంక్లిష్టతను కలిగి ఉంటుంది.

ఈ సమయం తీసుకునే విధానానికి బదులుగా, కాలపరిమితిలో ఫలితాన్ని లెక్కించగల ఇతర పరిష్కారాల గురించి మనం ఆలోచించాలి. ఇప్పుడు డైనమిక్ ప్రోగ్రామింగ్ మా సహాయానికి వస్తుంది. ప్రామాణిక మెట్రిక్ చైన్ గుణకారం సమస్యపై సమస్య కొద్దిగా వైవిధ్యం. ఇక్కడ ఈ సమస్యలో మనం మొదట 2 మూలకాలకు, తరువాత 3 మూలకాలకు సమాధానాన్ని లెక్కిస్తాము. కాబట్టి మేము సూచికలను పునరావృత ఫంక్షన్లో నిల్వ చేయడానికి రెండు వేరియబుల్స్ ఉంచుతాము, ఇది క్రమం యొక్క సరిహద్దును సూచిస్తుంది. తరువాత మేము క్రమాన్ని 2 భాగాలుగా విభజించాము. ఆపై ఈ రెండు ఉప సమస్యలను పరిష్కరించండి. మేము బేస్ కేసును కొట్టే వరకు ఈ ప్రక్రియ కొనసాగుతుంది. రెండు సూచికలు ఒకేలా ఉన్నప్పుడు ఇక్కడ బేస్ కేసు ఉంటుంది. ఈ ఉపప్రాబ్లమ్‌ల కోసం మేము సమాధానం లెక్కించినందున, ప్రారంభ సమస్యకు ఫలితాన్ని పొందడానికి మేము సమాధానాలను మిళితం చేస్తాము.

కోడ్

N సంఖ్యల గుణకారాల కనిష్ట మొత్తాన్ని కనుగొనడానికి C ++ కోడ్

#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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (N ^ 3), ఎందుకంటే N ^ 2 రాష్ట్రాలు ఉన్నాయి మరియు ప్రతి ఫలితాన్ని లెక్కించడానికి మనం సుమారు N సంఖ్య రాష్ట్రాలపై ఆధారపడి ఉంటాము. అందువలన సమయం సంక్లిష్టత బహుపది.

అంతరిక్ష సంక్లిష్టత

O (N ^ 2), ఎందుకంటే మేము 2D DP పట్టికను సృష్టించాము. అందువల్ల స్థల సంక్లిష్టత కూడా బహుపది.