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 the n-th element:
- If it is m, then the (n-1)th element is at most m/2. We recur for m/2 and n-1.
- If it is not m, then it 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 <iostream>using namespace std;// Recursive function to find the number of special// sequencesint 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 codeint main(){ int m = 10; int n = 4; cout << "Total number of possible sequences " << getTotalNumberOfSequences(m, n); return 0;}// This code is contributed by shivanisinghss2110 |
Java
// Java program to count total number// of special sequences of length n whereimport java.io.*;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)); }} |
Python3
#Python3 program to count total number of #special sequences of length n where #Recursive function to find the number of# special sequencesdef getTotalNumberOfSequences(m,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 res=(getTotalNumberOfSequences(m-1,n)+ getTotalNumberOfSequences(m//2,n-1)) return res#Driver Codeif __name__=='__main__': m=10 n=4 print('Total number of possible sequences:',getTotalNumberOfSequences(m,n)) #This code is contributed by sahilshelangia |
C#
// C# program to count total number // of special sequences of length n // where every element is more than // or equal to twice of previoususing 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
<?php// PHP program to count total // number of special sequences// of length n where// Recursive function to find // the number of special sequencesfunction getTotalNumberOfSequences($m, $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 $m = 10; $n = 4; echo("Total number of possible sequences "); echo (getTotalNumberOfSequences($m, $n));// This code is contributed by nitin mittal.?> |
Javascript
<script>// program to count total number of special sequences// of length n where // Recursive function to find the number of special// sequences function getTotalNumberOfSequences( m, 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 let m = 10; let n = 4; document.write ("Total number of possible sequences ", getTotalNumberOfSequences(m, n)); // This code is contributed by anikakapoor.</script> |
Output
Total number of possible sequences 4
Time Complexity: O(2m) in the worst case
Auxiliary Space: O(m), depth of recursion tree is m in the worst case.
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 <stdio.h>// DP based function to find the number of special// sequencesint 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<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 Codeint main(){ int m = 10; int n = 4; printf("Total number of possible sequences %d", getTotalNumberOfSequences(m, n)); return 0;} |
Java
// Efficient java program to count total number// of special sequences of length n whereimport java.io.*;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]; } // 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)); }} |
Python3
#Python3 program to count total number of #special sequences of length N where#DP based function to find the number# of special sequencedef 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<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} elif j==1: T[i][j]=i else: T[i][j]=T[i-1][j]+T[i//2][j-1] return T[m][n] #Driver Code if __name__=='__main__': m=10 n=4 print('Total number of possible sequences ',getTotalNumberOfSequences(m, n))#This code is contributed by sahilshelangia |
C#
// Efficient C# program to count total number // of special sequences of length n whereusing 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
<?php// PHP program to count total// number of special sequences// of length N where// DP based function to find// the number of special// sequencesfunction getTotalNumberOfSequences($m, $n){ // define T and build in bottom // manner to store number of // special sequences of length // n and maximum value m $T = array(array()); for ($i = 0; $i < $m + 1; $i++) { for ($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 or $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 $m = 10; $n = 4; echo "Total number of possible sequences ", getTotalNumberOfSequences($m, $n);// This code is contributed by anuj_67.?> |
Javascript
<script> // Efficient javascript program to count total number // of special sequences of length n where // DP based function to find the number of special // sequences function getTotalNumberOfSequences(m, n) { // define T and build in bottom manner to store // number of special sequences of length n and // maximum value m 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++) { // 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[parseInt(i/2, 10)][j-1]; } } return T[m][n]; } let m = 10; let n = 4; document.write("Total number of possible sequences "+ getTotalNumberOfSequences(m, n)); // This code is contributed rameshtravel07.</script> |
Output
Total number of possible sequences 4
Time Complexity : O(m x n)
Auxiliary Space : O(m x n)
This article is contributed by Bahubali. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
