CODEWITHSUNDEEP
c++overflowlong-integerfactorial
kss
kss

Reputation: 169

Factorial showing wrong answer in main. Computed correctly in function

Please explain the reason for the following behavior. Correct answer is after debug "3". I want that to be replicated in main after "4".

long int fact[501]={0};

long int factorial(int n)
{
    if(n==0 || n==1)
            return 1;
    if(fact[n]>1)
            return fact[n];

    if((fact[n]=n*factorial(n-1))>=1000000007)
    {       cout<<"2"<<endl<<fact[n]<<endl;
            fact[n]=fact[n]%1000000007;
            cout<<"3"<<endl<<fact[n]<<endl;
    }return fact[n];
}

int main()
{
    int n;
    cin>>n;
    cout<<"1"<<endl;
    cout<<factorial(n)<<endl;
    cout<<"4"<<endl;
    printf("%ld\n",fact[n]);
    return 0;
}

Upvotes: 1

Views: 179

Answers (2)

Jarod42
Jarod42

Reputation: 217398

With your compiler/platform, you have long int with 4 bytes so your value is truncated

With n >= 13, we have

fact[13] = 6227020800 which doesn't fit in a uint32_t

when truncated its new value goes to 1932053504 (and then 932053497 after modulo)

To fix your implementation you have to use uint64_t. (https://ideone.com/gQrxyW)

Upvotes: 0

R Sahu
R Sahu

Reputation: 206607

The output from the line

        cout<<"3"<<endl<<fact[n]<<endl;

does not necessarily correspond to n from main.

Try this modified version to see the difference:

#include <stdio.h>
#include <iostream>
using namespace std;

long int fact[501]={0};

long int factorial(int n)
{
    if(n==0 || n==1)
            return 1;
    if(fact[n]>1)
            return fact[n];

    if((fact[n]=n*factorial(n-1))>=1000000007)
    {       cout<<"2"<<endl<<fact[n]<<endl;
            fact[n]=fact[n]%1000000007;
            cout<<"3"<<endl<<n<<" "<<fact[n]<<endl;
    }return fact[n];
}

int main()
{
    int n;
    cin>>n;
    cout<<"1"<<endl;
    cout<<factorial(n)<<endl;
    cout<<"4"<<endl;
    printf("%ld\n",fact[n]);
    return 0;
}

Upvotes: 1

Related Questions