Sequences of given length where every element is more than or equal to twice of previous | DP based function to find the number of special sequences ; define T and build in bottom manner to store number of special sequences of length n and maximum value m ; Base case : If length of sequence is 0 or maximum value is 0 , there cannot exist any special sequence ; if length of sequence is more than the maximum value , special sequence cannot exist ; If length of sequence is 1 then the number of special sequences is equal to the maximum value For example with maximum value 2 and length 1 , there can be 2 special sequences { 1 } , { 2 } ; otherwise calculate ; Driver Code
function getTotalNumberOfSequences ( m , n ) { let T = new Array ( m + 1 ) ; for ( let i = 0 ; i < m + 1 ; i ++ ) { T [ i ] = new Array ( n + 1 ) ; for ( let j = 0 ; j < n + 1 ; j ++ ) { if ( i == 0 j == 0 ) T [ i ] [ j ] = 0 ; else if ( i < j ) T [ i ] [ j ] = 0 ; else if ( j == 1 ) T [ i ] [ j ] = i ; else T [ i ] [ j ] = T [ i - 1 ] [ j ] + T [ parseInt ( i / 2 , 10 ) ] [ j - 1 ] ; } } return T [ m ] [ n ] ; } let m = 10 ; let n = 4 ; document . write ( " " + getTotalNumberOfSequences ( m , n ) ) ;