0

Simran is running up a staircase with N steps, and can hop(jump) either 1 step, 2 steps or 3 steps at a time. You have to count how many possible ways Simran can run up to the stairs.

Input is N and output is the number of possible ways.

Why this code is not working with N>21?

#include<bits/stdc++.h>
using namespace std;
long long fact(int n)
{
 return (n==0) || (n==1) ? 1 : n* fact(n-1);
}
int main()
{
    int n;
    cin>>n;
    long long count=0;
   
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            for(int k=0;k<=n;k++)
            {
                if((i*1+j*2+k*3)==n)
                {
                 count+=fact(i+j+k)/(fact(i)*fact(j)*fact(k));
                }
            }
        }
    }
    cout<<count;
    return 0;
}
JohanC
  • 71,591
  • 8
  • 33
  • 66
lakshay sodhi
  • 1
  • are you sure you want to have a O(n^3) algorithm? consider using memoization to avoid repeating calculation – Alberto Sinigaglia Jul 23 '20 at 17:07
  • 2
    Unrelated: Be careful with the combination of `#include` and `using namespace std;`. Separately they can both cause trouble ([explanation](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) and [more explanation](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h)), but together they amplify each other's worst effects and turn [your code into a minefield](https://godbolt.org/z/9rT6Ws). – user4581301 Jul 23 '20 at 17:54
  • 1
    "#include using namespace std;" - Don't *ever* do that. – Jesper Juhl Jul 23 '20 at 18:21
  • @Berto99 It is much worse than O(n^3) - `fact` is not O(1). – user58697 Jul 23 '20 at 21:23

1 Answers1

2

If n is as high as 21, then fact(i+j+k) can go till 21 in worst case (i=21, j=0, k=0). Factorial of 21 is in the order of 10^19, which is beyond the range of long long. So it will overflow. I suggest you use Dynamic Programming here.

Het Pandya
  • 82
  • 1
  • 6