# Sequences of given length where every element is more than or equal to twice of previous

Given two integers m & n, find the number of possible sequences of length n such that each of the next element is greater than or equal to twice of the previous element but less than or equal to m.

Examples :

```Input : m = 10, n = 4
Output : 4
There should be n elements and value of last
element should be at-most m.
The sequences are {1, 2, 4, 8}, {1, 2, 4, 9},
{1, 2, 4, 10}, {1, 2, 5, 10}

Input : m = 5, n = 2
Output : 6
The sequences are {1, 2}, {1, 3}, {1, 4},
{1, 5}, {2, 4}, {2, 5}
```

As per the given condition the n-th value of the sequence can be at most m. There can be two cases for n-th element:

1. If it is m, then the (n-1)th element is at most m/2. We recur for m/2 and n-1.
2. If it is not m, then the n-1th element is at most is m-1. We recur for (m-1) and n.

The total number of sequences is the sum of the number of sequences including m and the number of sequences where m is not included. Thus the original problem of finding number of sequences of length n with max value m can be subdivided into independent subproblems of finding number of sequences of length n with max value m-1 and number of sequences of length n-1 with max value m/2.

## C++

 `// C program to count total number of special sequences ` `// of length n where ` `#include ` ` `  `// Recursive function to find the number of special ` `// sequences ` `int`  `getTotalNumberOfSequences(``int` `m, ``int` `n) ` `{ ` `    ``// A special sequence cannot exist if length ` `    ``// n is more than the maximum value m. ` `    ``if` `(m < n) ` `        ``return` `0; ` ` `  `    ``// If n is 0, found an empty special sequence ` `    ``if` `(n == 0) ` `        ``return` `1; ` ` `  `    ``// There can be two possibilities : (1) Reduce ` `    ``// last element value (2) Consider last element ` `    ``// as m and reduce number of terms ` `    ``return` `getTotalNumberOfSequences (m-1, n) + ` `           ``getTotalNumberOfSequences (m/2, n-1); ` `} ` ` `  `// Driver Code ` `int` `main() ` `{ ` `    ``int` `m = 10; ` `    ``int` `n = 4; ` `    ``printf``(``"Total number of possible sequences %d"``, ` `                   ``getTotalNumberOfSequences(m, n)); ` `    ``return` `0; ` `} `

## Java

 `// Java program to count total number  ` `// of special sequences of length n where ` `class` `Sequences ` `{ ` `    ``// Recursive function to find the number of special ` `    ``// sequences ` `    ``static` `int`  `getTotalNumberOfSequences(``int` `m, ``int` `n) ` `    ``{ ` `        ``// A special sequence cannot exist if length ` `        ``// n is more than the maximum value m. ` `        ``if``(m < n) ` `            ``return` `0``; ` `      `  `        ``// If n is 0, found an empty special sequence ` `        ``if``(n == ``0``) ` `            ``return` `1``; ` `      `  `        ``// There can be two possibilities : (1) Reduce ` `        ``// last element value (2) Consider last element ` `        ``// as m and reduce number of terms ` `        ``return` `getTotalNumberOfSequences (m-``1``, n) + ` `               ``getTotalNumberOfSequences (m/``2``, n-``1``); ` `    ``}    ` `     `  `    ``// main function ` `    ``public` `static` `void` `main (String[] args)  ` `    ``{ ` `        ``int` `m = ``10``; ` `        ``int` `n = ``4``; ` `        ``System.out.println(``"Total number of possible sequences "``+ ` `                       ``getTotalNumberOfSequences(m, n)); ` `    ``} ` `} `

/div>

## Python3

 `#Python3 program to count total number of  ` `#special sequences of length n where  ` `#Recursive function to find the number of ` `# special sequences ` `def` `getTotalNumberOfSequences(m,n): ` ` `  `    ``#A special sequence cannot exist if length  ` `    ``#n is more than the maximum value m.  ` `    ``if` `m

## C#

 `// C# program to count total number  ` `// of special sequences of length n  ` `// where every element is more than  ` `// or equal to twice of previous ` `using` `System; ` ` `  `class` `GFG ` `{ ` `    ``// Recursive function to find  ` `    ``// the number of special sequences ` `    ``static` `int` `getTotalNumberOfSequences(``int` `m, ``int` `n) ` `    ``{ ` `        ``// A special sequence cannot exist if length ` `        ``// n is more than the maximum value m. ` `        ``if``(m < n) ` `            ``return` `0; ` `     `  `        ``// If n is 0, found an empty special sequence ` `        ``if``(n == 0) ` `            ``return` `1; ` `     `  `        ``// There can be two possibilities : (1) Reduce ` `        ``// last element value (2) Consider last element ` `        ``// as m and reduce number of terms ` `        ``return` `getTotalNumberOfSequences (m-1, n) + ` `               ``getTotalNumberOfSequences (m/2, n-1); ` `    ``}  ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `Main ()  ` `    ``{ ` `        ``int` `m = 10; ` `        ``int` `n = 4; ` `        ``Console.Write(``"Total number of possible sequences "` `+ ` `                           ``getTotalNumberOfSequences(m, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal. `

## PHP

 ` `

Output:

```Total number of possible sequences 4
```

Note that the above function computes the same sub problems again and again. Consider the following tree for f(10, 4). Recursive Tree for m= 10 and N =4

We can solve this problem using dynamic programming.

## C++

 `// C program to count total number of special sequences ` `// of length N where ` `#include ` ` `  `// DP based function to find the number of special ` `// sequences ` `int`  `getTotalNumberOfSequences(``int` `m, ``int` `n) ` `{ ` `        ``// define T and build in bottom manner to store ` `        ``// number of special sequences of length n and ` `        ``// maximum value m ` `        ``int` `T[m+1][n+1]; ` `        ``for` `(``int` `i=0; i

## Java

 `// Efficient java program to count total number  ` `// of special sequences of length n where ` `class` `Sequences ` `{ ` `    ``// DP based function to find the number of special ` `    ``// sequences ` `    ``static` `int`  `getTotalNumberOfSequences(``int` `m, ``int` `n) ` `    ``{ ` `            ``// define T and build in bottom manner to store ` `            ``// number of special sequences of length n and ` `            ``// maximum value m ` `            ``int` `T[][]=``new` `int``[m+``1``][n+``1``]; ` `            ``for` `(``int` `i=``0``; i

## Python3

 `#Python3 program to count total number of  ` `#special sequences of length N where ` ` `  `#DP based function to find the number ` `# of special sequence ` `def` `getTotalNumberOfSequences(m,n): ` ` `  `    ``#define T and build in bottom manner to store  ` `    ``#number of special sequences of length n and  ` `    ``#maximum value m  ` `    ``T``=``[[``0` `for` `i ``in` `range``(n``+``1``)] ``for` `i ``in` `range``(m``+``1``)] ` `    ``for` `i ``in` `range``(m``+``1``): ` `        ``for` `j ``in` `range``(n``+``1``): ` ` `  `            ``#Base case : If length of sequence is 0  ` `            ``# or maximum value is 0, there cannot  ` `            ``#exist any special sequence ` `            ``if` `i``=``=``0` `or` `j``=``=``0``: ` `                ``T[i][j]``=``0` ` `  `            ``#if length of sequence is more than  ` `            ``#the maximum value, special sequence ` `            ``# cannot exist ` `            ``elif` `i

## C#

 `// Efficient C# program to count total number  ` `// of special sequences of length n where ` `using` `System; ` `class` `Sequences { ` `     `  `    ``// DP based function to find ` `    ``// the number of special ` `    ``// sequences ` `    ``static` `int` `getTotalNumberOfSequences(``int` `m, ``int` `n) ` `    ``{ ` `         `  `            ``// define T and build in ` `            ``// bottom manner to store ` `            ``// number of special sequences ` `            ``// of length n and maximum value m ` `            ``int` `[,]T=``new` `int``[m + 1, n + 1]; ` `             `  `            ``for` `(``int` `i = 0; i < m + 1; i++) ` `            ``{ ` `                ``for` `(``int` `j = 0; j < n + 1; j++) ` `                ``{ ` `                     `  `                    ``// Base case : If length  ` `                    ``// of sequence is 0 ` `                    ``// or maximum value is  ` `                    ``// 0, there cannot ` `                    ``// exist any special  ` `                    ``// sequence ` `                    ``if` `(i == 0 || j == 0) ` `                        ``T[i, j] = 0; ` `     `  `                    ``// if length of sequence ` `                    ``// is more than the maximum ` `                    ``// value, special sequence ` `                    ``// cannot exist ` `                    ``else` `if` `(i < j) ` `                        ``T[i,j] = 0; ` `     `  `                    ``// 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} ` `                    ``else` `if` `(j == 1) ` `                        ``T[i,j] = i; ` `     `  `                    ``// otherwise calculate ` `                    ``else` `                        ``T[i,j] = T[i - 1, j] + T[i / 2, j - 1]; ` `                ``} ` `            ``} ` `            ``return` `T[m,n]; ` `    ``} ` `     `  `    ``// Driver Code ` `    ``public` `static` `void` `Main ()  ` `    ``{ ` `        ``int` `m = 10; ` `        ``int` `n = 4; ` `        ``Console.WriteLine(``"Total number of possible sequences "``+ ` `                                ``getTotalNumberOfSequences(m, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by anuj_67. `

## PHP

 ` `

Output:

```4
```

Time Complexity : O(m x n)
Auxiliary Space : O(m x n)