daihan's blog

By daihan, 5 years ago, In English

Here is the problem link : https://www.hackerrank.com/challenges/down-to-zero-ii/problem

I used bottom up dp , but still getting stack overflow runtime error for input 1000000 . Can anyone help me , to point out where is wrong in my code :

code
  • Vote: I like it
  • +3
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this problem impossible to solve with Bottom up DP ? I solved using top down dp , using queue .

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    for $$$N=0$$$ you return $$$n$$$? shouldn't this be $$$0$$$?

    This is bottom up, gets accepted and its more or less in $$$O(n\sqrt{n})$$$:

    vector<int> res(1000001, 1000001);
    res[0] = 0;
    for (int i = 0; i < 1000001; i++) {
        res[i + 1] = min(res[i + 1], res[i] + 1);
        for (int j = 2; i * j < 1000001 && j <= i; j++) {
            res[i*j] = min(res[i*j], res[i] + 1);
        } 
    }
    
    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      This is $$$O(n\cdot log(n))$$$, as it can be written as $$$\sum_{i=1}^n\frac{n}{i} \simeq n \cdot ln(n) = O(n \cdot log(n))$$$

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, it should be 0. But still it overflow on 1000000

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        and you probably want to initialize $$$dp$$$ with $$$0$$$ and not $$$-1$$$ ?