K ஐ விட குறைவான தயாரிப்பு கொண்ட அனைத்து அடுத்தடுத்த நிகழ்வுகளையும் எண்ணுங்கள்  


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது ByteDance மூலதன ஒன்று கோட்நேஷன் தரவுத்தளங்கள் Expedia யாண்டேக்ஸ்
அணி டைனமிக் புரோகிராமிங்

“K ஐ விடக் குறைவான தயாரிப்புகளைக் கொண்ட அனைத்து அடுத்தடுத்த எண்ணிக்கையையும் எண்ணுங்கள்” என்ற சிக்கல் உங்களுக்கு முழு எண்களைக் கொடுக்கிறது என்று கூறுகிறது. கொடுக்கப்பட்ட உள்ளீட்டை விட குறைவான தயாரிப்பு கொண்ட அடுத்தடுத்த எண்ணிக்கையை இப்போது கண்டுபிடிக்கவும்.

உதாரணமாக  

K ஐ விட குறைவான தயாரிப்பு கொண்ட அனைத்து அடுத்தடுத்த நிகழ்வுகளையும் எண்ணுங்கள்முள்

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

விளக்கம்

கொடுக்கப்பட்ட k (= 11) ஐ விட குறைவான தயாரிப்பு கொண்ட 8 தொடர்ச்சிகள் உள்ளன. அடுத்தடுத்த படங்கள் மேலே உள்ள படத்தில் காட்டப்பட்டுள்ளன.

அணுகுமுறை  

சிக்கல் எங்களுக்கு முழு எண்களின் வரிசையையும், ஒரு முழு எண் கே யையும் வழங்கியுள்ளது. பின்னர் கே ஐ விடக் குறைவான உற்பத்தியைக் கொண்ட அடுத்தடுத்த எண்ணிக்கையைக் கண்டுபிடிக்கும்படி கூறப்படுகிறோம். ஆகவே, அடுத்தடுத்த, துணைக்குழுக்கள் அல்லது சப்ரேக்களைக் கையாளும் போதெல்லாம். ஒரு அப்பாவி அணுகுமுறை எப்போதுமே இந்த காட்சிகளை உருவாக்குவதோடு, உருவாக்கப்பட்ட வரிசை நம் நிலைமைகளை பூர்த்திசெய்கிறதா இல்லையா என்பதை சரிபார்க்கவும்.

இந்த அப்பாவியாக தீர்வு நிச்சயமாக நம் நேர வரம்பை மீறும். எனவே கொடுக்கப்பட்ட நேரக் கட்டுப்பாட்டின் கீழ் சிக்கலைத் தீர்க்க. நாங்கள் பயன்படுத்த வேண்டும் டைனமிக் புரோகிராமிங். எனவே இங்கே நாம் உள்ளீட்டு வரிசைக்கு மேல் பயணிப்போம். பயணத்தின் போது, ​​நாங்கள் ஒரே நேரத்தில் டிபி அட்டவணையை நிரப்புவோம். இந்த டிபி சிக்கலுக்கு எங்களிடம் இரண்டு மாநிலங்கள் உள்ளன, முதலாவது இப்போது வரை தயாரிப்பு மற்றும் இரண்டாவது உள்ளீட்டு வரிசைக்கான குறியீடாகும். நாங்கள் தயாரிப்புடன் தொடங்கி உள்ளீட்டு வரிசையிலிருந்து எண்கள் / உறுப்புகளுடன் தேவையான முடிவைப் பெற முடியுமா என்று சரிபார்க்கிறோம்.

மேலும் காண்க
அதிகபட்சம் 69 எண் லீட்கோட் தீர்வு

எங்கள் dp வரிசை செல் dp [i] [j] ஐ விட குறைவான தயாரிப்புகளைக் கொண்ட அடுத்தடுத்த எண்ணிக்கையைக் குறிக்கிறது மற்றும் உள்ளீட்டின் முதல் j கூறுகளைப் பயன்படுத்தி உருவாகிறது. எனவே dp [i] [j] ஐக் கண்டுபிடிப்பதற்கு, நாங்கள் dp [i / a [j]] [j] மற்றும் dp [i] [j-1] ஐ சார்ந்து இருக்கிறோம். ஆகவே, ஒரு [i]> i என்றால், இந்த உறுப்பை அடுத்தடுத்து எடுத்துக்கொள்வது ஒரு [i] தானாகவே K ஐ விட பெரியது என்று பொருள். இதனால் இந்த உறுப்பு கருதப்படாது. எனவே, கே-ஐ விட குறைவான தயாரிப்பு கொண்ட அனைத்து அடுத்தடுத்த நிகழ்வுகளையும் நாம் கணக்கிடுகிறோம்.

குறியீடு  

K ஐ விட குறைவான தயாரிப்பு கொண்ட அனைத்து அடுத்தடுத்த நிகழ்வுகளையும் எண்ணுவதற்கு C ++ குறியீடு

#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 ஐக் கொண்டுள்ளன, இதனால் நேர சிக்கலானது பல்லுறுப்புக்கோவையாகும்.

விண்வெளி சிக்கலானது

ஓ (என் * கே), ஏனெனில் நாங்கள் N * K கலங்களுடன் 2D DP அட்டவணையை உருவாக்கியுள்ளோம். இதனால் விண்வெளி சிக்கலானது பல்லுறுப்புக்கோவையாகும்.