Number of Possible Sequences


  • 0
    A

    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]

  • 0

    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.


  • 0
    A

    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 :)


  • 0

    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;
    }
    

Log in to reply
 

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