K भन्दा कम उत्पादन भएको सबै उप-परिच्छेदहरू गणना गर्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ बाइटडेन्स राजधानी एक CodeNation डाटाब्रिक्स Expedia Yandex
एरे डायनामिक प्रोग्रामिंग

समस्या "K भन्दा कम उत्पादन भएको सबै उपगणनाहरू गणना गर्नुहोस्" भन्छ कि तपाईंलाई पूर्णांकको एरे दिइन्छ। अब उप-घटनाहरूको संख्या फेला पार्नुहोस् जुनसँग एउटा इनपुट K भन्दा कम उत्पादन छ।

उदाहरणका

K भन्दा कम उत्पादन भएको सबै उप-परिच्छेदहरू गणना गर्नुहोस्

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

स्पष्टीकरण

त्यहाँ ११ उप-उपक्रमहरू छन् जुन दिएका के भन्दा कम उत्पादन छ (= product)। उप-दृश्यहरू माथिको छविमा देखाईएको छ।

दृष्टिकोण

समस्याले हामीलाई पूर्णांकको अनुक्रम प्रदान गरेको छ, र एक पूर्णांक के। त्यसोभए हामीलाई अनुगमनहरूको संख्या पत्ता लगाउन भनिएको छ जसको K भन्दा कमको उत्पादन छ। त्यसैले, जब हामी उप-परिदृश्यहरू, उपसमूहहरू, वा subarrays सम्झौता गर्छौं। एक भोलाउने दृष्टिकोण सँधै यी अनुक्रमहरू उत्पन्न गर्न को लागी हो र त्यसपछि जाँच गर्नुहोस् कि उत्पन्न अनुक्रमले हाम्रो सर्तहरू सन्तुष्ट पार्छ कि हुँदैन?

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

हाम्रो डीपी एर्रे सेल डीपी [i] [j] उप-सences्ख्याहरूको सot्केत गर्दछ जुन म भन्दा कम उत्पादन गर्दछ र इनपुटको पहिलो जे तत्व प्रयोग गरेर गठन गरिन्छ। त्यसो भए dp खोज्नका लागि [i] [j], हामी dp [i / a [j]] [j] र dp [i] [j-1] मा निर्भर छौं। त्यसोभए यदि एउटा [i]> i, यस एलिमेन्टलाई अर्को भागमा लिनु भनेको यसको मतलब यो हुन्छ कि a [i] आफु 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

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

समय जटिलता

O (N * K), किनकि त्यहाँ दुई राज्यहरू छन् एउटा इनपुट एर्रेको लागि सूचकांक हो र अर्को अर्को अनुगामी सीमाको उत्पादन हो। तिनीहरूसँग माथिल्लो बाउन्ड एन र के छ, यसैले समय जटिलता बहुपद हो।

ठाउँ जटिलता

O (N * K), किनभने हामीले ND K सेलहरूको साथ 2D DP टेबल सिर्जना गर्‍यौं। यसैले अन्तरिक्ष जटिलता पनि बहुपद हो।