दिलेली लांबीचे अनुक्रम जिथे प्रत्येक घटक मागीलपेक्षा दोनदा किंवा त्यापेक्षा जास्त असेल


अडचण पातळी सोपे
वारंवार विचारले ऐक्सचर ऍमेझॉन CodeNation फेसबुक Google पोपल Qualcomm
विभाजित आणि विजय डायनॅमिक प्रोग्रामिंग

समस्या “दिलेल्या लांबीचे अनुक्रम जिथे प्रत्येक घटक मागीलपेक्षा दुप्पट किंवा समान असेल” आम्हाला दोन पूर्णांक एम आणि एन प्रदान करतात. येथे m अनुक्रमात अस्तित्त्वात असलेली सर्वात मोठी संख्या आहे आणि आवश्यक क्रमातील घटकांची संख्या असणे आवश्यक आहे. अनुक्रमात आणखी एक अट घातली आहे, ती म्हणजे प्रत्येक घटक मागील घटकापेक्षा दोनदा किंवा त्यापेक्षा जास्त असावा. सर्व अटी पूर्ण केल्या गेलेल्या क्रमांची एकूण संख्या शोधा.

उदाहरण

n = 3, m = 6
4

स्पष्टीकरण

तेथे दिलेल्या 4 सीक्वेन्सस दिलेल्या अटींमध्ये तयार केल्या जाऊ शकतात: (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 3, 6).

दृष्टीकोन

समस्या आम्हाला दिलेल्या लांबीच्या अनुक्रमांची एकूण संख्या शोधण्यास सांगते जिथे प्रत्येक घटक मागीलपेक्षा दोनदा किंवा त्यापेक्षा जास्त असेल. एक निष्कलंक निराकरण ज्यामध्ये उच्च कालावधीची गुंतागुंत असते ते सर्व लांबीचे क्रम तयार करणे असू शकते n. घटकांनी चढत्या क्रमाने अनुसरण केले पाहिजे आणि जास्तीत जास्त संख्या ओलांडू नये m. परंतु प्रत्येक घटक मागीलपेक्षा दुप्पट किंवा त्यापेक्षा जास्त असावा ही वस्तुस्थिती आपण एकत्रित केली असती तर अधिक कार्यक्षम निराकरण होऊ शकले असते. अशा प्रकारे आपण रिकर्सीव्ह फॉर्म्युला लिहू शकतो. आम्ही निवडल्यास नंतर आपल्याला लांबीचा क्रम शोधावा लागेल एन-एक्सएनयूएमएक्स आणि जास्तीत जास्त घटक मी / 2. अन्यथा आपल्याला लांबीसह क्रम शोधणे आवश्यक आहे आणि जास्तीत जास्त घटक M-1. जरी हा दृष्टिकोन पूर्वीच्या चर्चेपेक्षा थोडा अधिक कार्यक्षम आहे. हे देखील वेळ घेणारे आहे.

दिलेली लांबीचे अनुक्रम जिथे प्रत्येक घटक मागीलपेक्षा दोनदा किंवा त्यापेक्षा जास्त असेल

ज्या प्रकरणांमध्ये आमच्याकडे रिकर्सिव फॉर्म्युला आहे, आम्ही वापरतो डायनॅमिक प्रोग्रामिंग. आम्ही फक्त वरील गोष्टी लक्षात ठेवू रिकर्सिव ज्यावर आपण चर्चा केली. या प्रकरणात, आपल्याकडे 2 राज्ये आहेत. प्रथम जास्तीत जास्त संख्या आणि दुसरी अनुक्रमांची लांबी.

कोड

दिलेली लांबीचे अनुक्रम शोधण्यासाठी सी ++ कोड जिथे प्रत्येक घटक मागीलपेक्षा दोनदा किंवा त्यापेक्षा अधिक असेल

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

int main()
{
    int n = 3, m = 6;
    int dp[m+1][n+1];
    memset(dp, 0, sizeof dp);
    for(int i=0;i<=m;i++)
        dp[i][0] = 1;
    int ans = 0;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            // we pick the current element
            dp[i][j] = dp[i/2][j-1];
            // we ignore the current element
            dp[i][j] += dp[i-1][j];
        }
    }
    cout<<dp[n][m];
}
4

दिलेल्या लांबीचा क्रम शोधण्यासाठी जावा कोड जिथे प्रत्येक घटक मागीलपेक्षा दोनदा किंवा त्यापेक्षा जास्त असेल

import java.util.*;
class Main{
  public static void main(String[] args)
  {
      int n = 3, m = 6;
      int dp[][] = new int[m+1][n+1];
      for(int i=0;i<=n;i++)
      	for(int j=0;j<=m;j++)
      		dp[i][j] = 0;
      for(int i=0;i<=m;i++)
          dp[i][0] = 1;
      for(int i=1;i<=m;i++){
          for(int j=1;j<=n;j++){
              // we pick the current element
              dp[i][j] = dp[i/2][j-1];
              // we ignore the current element
              dp[i][j] += dp[i-1][j];
          }
      };
    System.out.print("dp[n][m]");
  }
}
4

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

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

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

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

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