के पेक्षा कमी उत्पादन असलेली सर्व उपगणने मोजा


अडचण पातळी सोपे
वारंवार विचारले बाइट डान्स कॅपिटल वन CodeNation डेटाबे्रिक्स यामध्ये यांडेक्स
अरे डायनॅमिक प्रोग्रामिंग

“के पेक्षा उत्पादन कमी असलेल्या सर्व अनुक्रमांची मोजणी करा” ही समस्या सांगते की आपल्याला पूर्णांकांची अ‍ॅरे दिली आहे. आता दिलेल्या इनपुट के पेक्षा कमी उत्पादन असलेले उपसंख्यांची संख्या शोधा.

उदाहरण

के पेक्षा कमी उत्पादन असलेली सर्व उपगणने मोजा

a[] = {1, 2, 3, 4, 5}
k = 8
Number of subsequences less than 8: 11

स्पष्टीकरण

अशी 11 उपके आहेत जी दिलेली (= 8) पेक्षा कमी उत्पादन आहेत. उपरोक्त प्रतिमा वरील प्रतिमेमध्ये दर्शविली आहेत.

दृष्टीकोन

समस्येमुळे आम्हाला पूर्णांकांचा क्रम आणि एक पूर्णांक के. प्रदान केले गेले आहे. त्यानंतर आम्हाला असे सांगितले जाते की के. पेक्षा कमी उत्पादन असणाqu्या अनुक्रमांची संख्या शोधू. तेव्हा, जेव्हा जेव्हा आम्ही उपखंडासह, उपसमूह किंवा उपनारा व्यवहार करतो. एक भोळे दृष्टिकोन नेहमीच हे अनुक्रम व्युत्पन्न करणे आणि नंतर व्युत्पन्न केलेला अनुक्रम आमच्या शर्ती पूर्ण करतो की नाही ते तपासा.

हे निराकरण समाधान निश्चितपणे आपली वेळ मर्यादा ओलांडेल. तर दिलेल्या मुदतीच्या अंतर्गत समस्येचे निराकरण करण्यासाठी. आम्हाला वापरणे आवश्यक आहे डायनॅमिक प्रोग्रामिंग. येथे आपण इनपुट अ‍ॅरे वर जाऊ. ट्रॅव्हर्सल दरम्यान आम्ही एकाच वेळी डीपी टेबल भरत आहोत. या डीपी समस्येसाठी आमच्याकडे दोन राज्ये आहेत, पहिले आत्तापर्यंतचे उत्पादन आणि दुसरे इनपुट अ‍ॅरेसाठी निर्देशांक आहे. आम्ही उत्पादनासह प्रारंभ करतो आणि आम्ही इनपुट अ‍ॅरेमधून क्रमांक / घटकांसह आवश्यक परिणाम मिळवू शकतो की नाही हे तपासतो.

आमचा डीपी अ‍ॅरे सेल डीपी [i] [जे] उपखंडांची संख्या सूचित करते ज्याचे उत्पादन मीपेक्षा कमी आहे आणि इनपुटच्या पहिल्या जे घटकांचा वापर करून तयार केले आहेत. तर डीपी [i] [जे] शोधण्यासाठी, आम्ही डीपी [i / a [जे]] [जे] आणि डीपी [i] [जे -१] वर अवलंबून आहोत. म्हणून जर [i]> मी, हा घटक अनुक्रमात घेतल्याचा अर्थ असा होईल की एक [i] स्वतः के पेक्षा मोठा आहे. अशा प्रकारे या घटकाचा विचार केला जाणार नाही. अशा प्रकारे आम्ही के पेक्षा कमी उत्पादन असलेली सर्व उपगणने मोजू शकतो.

कोड

के पेक्षा कमी उत्पादन असलेली सर्व उपगणने मोजण्यासाठी सी ++ कोड

#include <bits/stdc++.h>
using namespace std;

int main(){
    int a[] = {1, 2, 3, 4, 5};
    int n = (sizeof a)/(sizeof a[0]);
    int k = 8;
    int dp[k][n+1];
    memset(dp, 0, sizeof(dp));

    for (int i=1;i<k;i++){
        for (int j=1;j<=n;j++){
            dp[i][j] = dp[i][j-1];
            if (a[j-1] <= i && a[j-1] > 0)
                dp[i][j] += dp[i/a[j-1]][j-1] + 1;
        }
    }

    cout<<dp[k-1][n];
}
11

के पेक्षा कमी उत्पादन असणार्‍या सर्व अनुक्रमांची गणना करण्यासाठी जावा कोड

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int a[] = {1, 2, 3, 4, 5};
      int n = a.length;
      int k = 8;
      int dp[][] = new int[k][n+1];
      for(int i=0;i<k;i++)
      	for(int j=0;j<n+1;j++)
      		dp[i][j] = 0;

      for (int i=1;i<k;i++){
          for (int j=1;j<=n;j++){
              dp[i][j] = dp[i][j-1];
              if (a[j-1] <= i && a[j-1] > 0)
                  dp[i][j] += dp[i/a[j-1]][j-1] + 1;
          }
      }
    System.out.println(dp[k-1][n]);
  }
}
11

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन * के), कारण तेथे दोन राज्ये आहेत एक इनपुट अ‍ॅरेची अनुक्रमणिका आहे आणि दुसरे अनुगामी मर्यादेचे उत्पादन आहेत. त्यांच्याकडे वरच्या बाउंड एन आणि के असतात, ज्यामुळे वेळ जटिलता बहुपद असते.

स्पेस कॉम्प्लेक्सिटी

ओ (एन * के), कारण आम्ही एन * के सेलसह 2 डी डीपी टेबल तयार केला आहे. अशा प्रकारे जागेची जटिलता देखील बहुपदी आहे.