We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. P-sequences
  5. Discussions

P-sequences

Sort 12 Discussions, By:

  • thecodingsoluti2
     + 0 comments

    Here is P-sequences problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-p-sequences-problem-solution.html

  • brunopaulsen
     + 0 comments

    The algorithm is correct

    Still it will not work for very large number TestCases: 10,11,13,16,17 and 18. They exceed computational capacity of 53bit integers. Then, a special multiplication procedure will be needed in order to get the correct modulus without errors induced by those really really really really big numbers,,,,,

    function pSequences(n, p) {
    // Write your code here
    const MOD = 1000000000+7
    let root = parseInt(Math.sqrt(p)),
        last = root*2-((root*(root+1)>p)?2:1),
        qtty = [], val=[], calc=[], i=0, j=last, accum=0, size=last+1
    while (accum < p) calc[j--] = (accum += (val[i] = (qtty[i++] = (parseInt(p/parseInt(p/(accum+1))) - accum))))
    while(n-->=2) {
        let next = new Array(size)
        accum = 0
        for(i=0,j=last;i<=last;i++,j--) next[j] = (accum = (accum + (val[i] = ((qtty[i] * calc[i])%MOD)))%MOD)
        calc = next
    }
    return accum % MOD
}

  • er_vikramsnehi
     + 0 comments

    In JavaScript, 

    var result=0;
    for(var i=1;i<=n;i++)
    {
        for(var j=1;j<=n;j++)
            {
                if(i*j<=p)
                {
                    result = result+1;
                }
            }
    }
    return(result)

    something is not working here.

  • ammar_kothari
     + 0 comments

    Hello,

    I don't know how to speed up the runtime of my solution. I think I am missing a way to enumerate all the possible subsequences. If you have any ideas on how I can reduce the runtime, I would really appreciate it.

    One idea I had is to create a map of the parameters (length of sequence, max value, and starting number) that can be used to look up values instead of running through the recursion each time. This seems a little too complicated, but I am currently trying it out.

    Quick Summary of Code: Use recursion to determine the number of subsequences that are valid given a starting number for the sequence. For each recursion, a shorter sequence with a different inint

    #include <bits/stdc++.h>

using namespace std;

int pSequences2(int n, int p, int prev_num) {
    int count = 0;
    if (n == 1) {
        // if its the last number
        // all subsequent numbers are those that are less than p/prev
        count += (p/prev_num);
    }
    else {
        for (int i_p=1; i_p<=p; i_p++) {
            if (prev_num*i_p<=p) {
                count += pSequences2(n-1, p, i_p);
            }
            else {
                break;
            }
        }
    }
    return count;
}


int pSequences(int n, int p) {
    int count = 0;
    // generate all possible first values of sequence
    count = pSequences2(n, p, 0);
    return count;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));
    vector< vector<int> > seqs;

    int n;
    cin >> n;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');

    int p;
    cin >> p;
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    
    int result = pSequences(n, p);
    
    fout << result << "\n";

    fout.close();

    return 0;
}

  • harshchaplot11
     + 0 comments

    What is the problem with this and in testcase 2 the input is 3 and 2 and the expected output is 5 which is logically impossible. The ans must be 3 and my code is also giving ans as 3.

    include

    include

    int main() { int n,p,i,j,mul,count=0; scanf("%d %d",&n,&p); for(i=1;i

    }

Load more conversations