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 મેળવ્યા હોત. આ રીતે બંને રીતે આપણે સરખું પરિણામ મેળવી લીધું હોત.

અભિગમ  

સમસ્યા અમને ન્યુનત્તમ રકમ શોધવા માટે પૂછે છે જે મળી શકે કે તમે જોડીમાં સંખ્યાને ગુણાકાર કરવાનું ચાલુ રાખો અને પછી તેમનો ઉમેરો કરો. સમસ્યા હલ કરવા માટે નિષ્કપટ અભિગમનો ઉપયોગ કરવામાં આવે છે રિકર્ઝન. બધા ક્રમચયો ઉત્પન્ન કરો અને પછી ધ્યાનમાં લો કે આ ક્રમચયો સૂચકાંકો સૂચવે છે જે જોડીમાં ગુણાકાર કરવા જોઈએ. પરંતુ આ અભિગમ સમય માંગી રહ્યો છે કારણ કે ક્રમચયની પે generationીમાં સમયની જટિલતા હોય છે.

આ સમય માંગીતી અભિગમને બદલે, આપણે કોઈપણ અન્ય સમાધાનો વિશે વિચારવું જોઈએ જે સમય મર્યાદા હેઠળ પરિણામની ગણતરી કરવામાં સક્ષમ છે. હવે ડાયનેમિક પ્રોગ્રામિંગ અમારી સહાય માટે આવે છે. સમસ્યા પ્રમાણભૂત મેટ્રિક ચેઇન ગુણાકારની સમસ્યાનું થોડું ભિન્નતા છે. અહીં આ સમસ્યામાં આપણે પહેલા 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

જાવા કોડ શોધવા માટે નંબરોના ગુણાકારની ન્યૂનતમ રકમ

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), કારણ કે ત્યાં એન ^ 2 રાજ્યો છે અને દરેક માટે પરિણામની ગણતરી કરવા માટે આપણે આશરે N રાજ્યોની સંખ્યા પર આધારીત છીએ. આમ સમય જટિલતા બહુપદી છે.

અવકાશ જટિલતા

ઓ (એન ^ 2), કારણ કે આપણે 2D DP કોષ્ટક બનાવ્યું છે. આમ જગ્યા જટિલતા પણ બહુપદી છે.