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
# | User | Rating |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 161 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 152 |
8 | pajenegod | 146 |
9 | BledDest | 144 |
10 | Um_nik | 143 |
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 :
# include < bits/stdc++. h >
using namespace std;
int n,q,i,j;
int dp[2000000];
int flag[2000000];
int recursion(int N) {
// cout<<N<<endl;
if(N==0) return 0; if(dp[N]!=-1) return dp[N]; int x=recursion(N-1)+1; int y=2147483647; for(int i=2; i*i<=N; i++) if(N%i==0) y=min(y,recursion(N/i)+1); dp[N]=min(x,y); return dp[N];
}
int main() {
memset(dp,-1,sizeof(dp)); scanf("%d",&q); while(q--) { scanf("%d",&n); printf("%d\n",recursion(n)); } return 0;
}
Name |
---|
Is this problem impossible to solve with Bottom up DP ? I solved using top down dp , using queue .
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})$$$:
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))$$$
oh yes you are right.
Yeah, it should be 0. But still it overflow on 1000000
and you probably want to initialize $$$dp$$$ with $$$0$$$ and not $$$-1$$$ ?