# Number of Possible Sequences

• Let's define a sequence S of positive integers where each element is either equal to twice the preceding element (or) more than twice the preceding element in that sequence.
Given two parameters, `len` and `max_value`, write a function which returns the total number of such sequences possible. The sequence should contain exactly `len` number of elements and the maximum value in the sequence cannot exceed `max_value` ( but can be equal to it )

An example, just in case, the question is unclear.

`len` = 4 `max_value` = 10

The function should return 4.
because the possible sequences are:

``````[1,2,4,8]
[1,2,4,9]
[1,2,4,10]
[1,2,5,10]``````

• Why is `[1,1,1,1]` not a valid sequence? And why is `[1,2,4,8]` valid? You mentioned each element is either equal to or more than twice the preceding element.

• I meant it as equal to twice the preceding element or more than twice the preceding element. So, [1,1,1,1] clearly not a member of the defined sequence.
Accounting for equal to twice the preceding element, [1,2,4,8] is a possible sequence.
I'll clear that up in the question. Thanks :)

• I think this is a variation of the "Longest Increasing Subsequence" problem, we can use dynamic programming to solve it, time complexity O(n^2). Following is my solution, hope the comments help.

So if len = 4, max = 10, here is what we get:

nums[i] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

dp[i][0] = {1, 2, 2, 3, 3, 3, 3, `4`, `4`, `4`}

dp[i][1] = {0, 1, 1, 1, 1, 2, 2, `1`, `1`, `2`}

``````public int countSequences(int len, int max) {
// dp[i][0] is the length of the longest possible sequence till i.
// dp[i][1] is how many numbers help current number i
// form the longest sequence and they are less than i / 2
int[][] dp = new int[max + 1][2];

// initialize first number
dp[1][0] = 1;

for (int i = 2; i <= max; i++) {
// by default, each number can form a sequence
// and the length is 1
dp[i][0] = 1;

for (int j = 1; j < i; j++) {
if (i >= j * 2) {
if (dp[i][0] < dp[j][0] + 1) {
// a longer sequence is found
// reset the count to 1
dp[i][0] = dp[j][0] + 1;
dp[i][1] = 1;
} else if (dp[i][0] == dp[j][0] + 1) {
// same length sequence
// update the count by +1
dp[i][1]++;
}
}
}
}

// finally get the total count of sequences whose length is len
int count = 0;
for (int i = 1; i <= max; i++) {
if (dp[i][0] == len) {
count += dp[i][1];
}
}

return count;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.