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

Difficulty Level Easy
Frequently asked in Accenture Amazon CodeNation Facebook Google PayPal Qualcomm
Divide and Conquer Dynamic ProgrammingViews 3603

The problem “Sequences of given length where every element is more than or equal to twice of previous” provides us with two integers m and n. Here m is the largest number that can exist in the sequence and n is the number of elements that must be present in the required sequence. There is one more condition imposed on the sequence, that is each element should be more than or equal to twice to the previous element. Find out the total number of sequences such that all the conditions are met.

Example

n = 3, m = 6
4

Explanation

There are 4 sequences which can be made under given conditions: (1, 2, 4), (1, 2, 5), (1, 2, 6), (1, 3, 6).

Approach

The problem asks us to find the total number of sequences of a given length where every element is more than or equal to twice of previous. A naive solution which has high time complexity can be to generate all the sequences of length n. The elements should follow the ascending order and the maximum number should not exceed m. But a more efficient solution could have been if we incorporated the fact that each element should be more than or equal to twice the previous. Thus we can write a recursive formula. If we pick m then we have to find the sequence with length n-1 and maximum element m/2. Else we need to find the sequence with length n and maximum element m-1. Even though this approach is a bit more efficient than the previously discussed one. This also is time-consuming.

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

In the cases where we do have a recursive formula, we use dynamic programming. We will simply memoize the above recursive solution which we discussed. In this case, we have 2 states. The first is the maximum number and the other is the length of the sequence.

Code

C++ code to find sequences of given length where every element is more than or equal to twice of previous

#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

Java code to find Sequences of given length where every element is more than or equal to twice of previous

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

Complexity Analysis

Time Complexity

O(N*M), because the states for the problem are the length of the sequence and the maximum number which can be considered. Thus the time complexity is polynomial.

Space Complexity

O(N*M), because we have created a 2D DP table to store the intermediate results. The space complexity is also polynomial.

Translate »