K से कम उत्पाद वाले सभी अनुवर्ती गणना करें


कठिनाई स्तर आसान
में अक्सर पूछा ByteDance एक राजधानी कोडेशन डाटब्रिक्स Expedia Yandex
ऐरे गतिशील प्रोग्रामिंग

समस्या "के से कम उत्पाद वाले सभी बाद की गणना" बताती है कि आपको पूर्णांक की एक सरणी दी गई है। अब उन अनुवर्ती संख्याओं का पता लगाएं, जिनमें किसी दिए गए इनपुट K से कम उत्पाद है।

उदाहरण

K से कम उत्पाद वाले सभी अनुवर्ती गणना करें

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

व्याख्या

11 अनुवर्ती हैं, जिनमें दिए गए k (= 8) से कम उत्पाद हैं। इसके बाद के संस्करण की छवि में दिखाया गया है।

दृष्टिकोण

समस्या ने हमें पूर्णांकों के अनुक्रम के साथ प्रदान किया है, और एक पूर्णांक के। तब हमें बाद के संख्याओं को खोजने के लिए कहा जाता है जिनके पास के से कम का उत्पाद होता है। इसलिए, जब भी हम अनुवर्ती, सबसेट या उप-संस्करण से निपटते हैं। एक भोली दृष्टिकोण हमेशा इन दृश्यों को उत्पन्न करने के लिए होता है और फिर जाँचता है कि क्या उत्पन्न अनुक्रम हमारी स्थितियों को संतुष्ट करता है या नहीं?

यह भोला समाधान निश्चित रूप से हमारी समय सीमा को पार कर जाएगा। तो दिए गए समय की कमी के तहत समस्या को हल करने के लिए। हम उपयोग करने के लिए आवश्यक हैं गतिशील प्रोग्रामिंग। इसलिए यहां हम इनपुट ऐरे से आगे बढ़ेंगे। ट्रैवर्सल के दौरान, हम डीपी टेबल एक साथ भरेंगे। इस डीपी समस्या के लिए हमारे पास दो राज्य हैं, पहला अब तक का उत्पाद है और दूसरा इनपुट ऐरे के लिए सूचकांक है। हम उत्पाद के साथ शुरू करते हैं और जांचते हैं कि क्या हम इनपुट ऐरे से संख्याओं / तत्वों के साथ आवश्यक परिणाम प्राप्त कर सकते हैं।

हमारी dp सरणी सेल dp [i] [j] उन अनुवर्ती संख्याओं को दर्शाती है, जिनके उत्पाद i से कम हैं और इनपुट के पहले j तत्वों का उपयोग करके बनाए गए हैं। तो dp [i] [j] खोजने के लिए, हम dp [i / a [j]] [j] और dp [i] [j-१] पर निर्भर हैं। इसलिए अगर एक [i]> i, इस तत्व को बाद में ले जाने का मतलब यह होगा कि एक [i] खुद K से बड़ा है। इसलिए इस तत्व पर विचार नहीं किया जाएगा। तो यह है कि हम कैसे K से कम उत्पाद वाले सभी बाद की गणना करते हैं।

कोड

C ++ कोड की तुलना में K से कम उत्पाद वाले सभी बाद की गणना करने के लिए

#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

जावा कोड K से कम उत्पाद वाले सभी बाद की गणना करने के लिए

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

जटिलता विश्लेषण

समय जटिलता

ओ (एन * के), क्योंकि इनपुट ऐरे के लिए इंडेक्स होने के दो राज्य हैं और दूसरे के बाद की सीमा का उत्पाद है। उनके पास एक ऊपरी बाध्य एन और के है, इस प्रकार समय जटिलता बहुपद है।

अंतरिक्ष जटिलता

ओ (एन * के), क्योंकि हमने N * K कोशिकाओं के साथ एक 2D DP तालिका बनाई है। इस प्रकार अंतरिक्ष की जटिलता भी बहुपद है।