આપેલ લંબાઈનો ક્રમ જ્યાં દરેક તત્વ પાછલા કરતા બે વાર કરતા વધારે અથવા બરાબર હોય છે


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એક્સેન્ચર એમેઝોન કોડનેશન ફેસબુક Google પેપાલ ક્યુઅલકોમ
વિભાજીત અને વિજય ડાયનેમિક પ્રોગ્રામિંગ

સમસ્યા “આપેલ લંબાઈના સિક્વન્સ કે જ્યાં દરેક તત્વ પહેલાના કરતા બમણા અથવા બરાબર હોય છે” અમને બે પૂર્ણાંકો એમ અને એન પૂરા પાડે છે. અહીં m ક્રમાંકમાં અસ્તિત્વમાં હોઈ શકે તેવી સૌથી મોટી સંખ્યા છે અને તે તત્વોની સંખ્યા છે જે આવશ્યક ક્રમમાં હાજર હોવા આવશ્યક છે. અનુક્રમ પર વધુ એક શરત લાદવામાં આવી છે, તે એ છે કે દરેક તત્વ પાછલા તત્વ કરતા બમણા અથવા તેના કરતા વધુ હોવું જોઈએ. ક્રમની કુલ સંખ્યા શોધો જેમ કે બધી શરતો પૂરી થાય છે.

ઉદાહરણ

n = 3, m = 6
4

સમજૂતી

ત્યાં 4 સિક્વન્સ છે જે આપેલ શરતો હેઠળ બનાવી શકાય છે: (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 3, 6).

અભિગમ

સમસ્યા અમને આપેલ લંબાઈના ક્રમની કુલ સંખ્યા શોધવા માટે પૂછે છે જ્યાં દરેક તત્વ અગાઉના કરતા બમણા કરતા વધારે અથવા સમાન હોય છે. એક નિષ્કપટ સોલ્યુશન જેમાં ઉચ્ચ સમયની જટિલતા હોય છે તે લંબાઈના તમામ ક્રમ ઉત્પન્ન કરી શકે છે n. તત્વોએ ચડતા ક્રમનું પાલન કરવું જોઈએ અને મહત્તમ સંખ્યા કરતાં વધુ ન હોવી જોઈએ m. પરંતુ જો આપણે એ તથ્યને સમાવી લીધું હોત કે દરેક તત્વ અગાઉના બમણા કરતા વધારે અથવા બરાબર હોવું જોઈએ, તો વધુ કાર્યક્ષમ ઉપાય હોઈ શકે. આમ આપણે રિકરિવ ફોર્મ્યુલા લખી શકીએ છીએ. જો આપણે પસંદ કરીએ તો પછી આપણે લંબાઈ સાથેનો ક્રમ શોધવો પડશે n-1 અને મહત્તમ તત્વ મી / 2. બાકી આપણે લંબાઈ સાથેનો ક્રમ શોધવાની જરૂર છે અને મહત્તમ તત્વ મી-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 DP કોષ્ટક બનાવ્યું છે. અવકાશ જટિલતા પણ બહુપદી છે.