Strange outcome after passing array

77 Views Asked by At

Here is the code to calculate nCr % P by using Fermat's little theorem

long long power(long long x, long long y, long long p) 
{ 
    long long res = 1;      // Initialize result 

    x = x % p;  // Update x if it is more than or 
            // equal to p 

    while (y > 0) 
    { 
    // If y is odd, multiply x with result 
        if (y & 1) 
           res = (res*x) % p; 

         // y must be even now 
         y = y>>1; // y = y/2 
         x = (x*x) % p; 
    } 
    return res; 
} 

// Returns n^(-1) mod p 
long long modInverse(long long n, long long p) 
{ 
    return power(n, p-2, p); 
} 

// Returns nCr % p using Fermat's little 
// theorem. 
long long nCrModPFermat(long long n, long long r, long long p) 
{ 
    // Base case 
   if (r==0) 
       return 1; 

    // Fill factorial array so that we 
    // can find all factorial of r, n 
    // and n-r 

    long long fac[n+1]; 
    fac[0] = 1; 
    for (long long i=1 ; i<=n; i++) 
        fac[i] = fac[i-1]*i%p; 

     return (fac[n]* modInverse(fac[r], p) % p * 
            modInverse(fac[n-r], p) % p) % p; 
} 

To optimise the code, I precalculated the fac[] array and passed it as an argument in the nCrModPFermat() function:

long long nCrModPFermat(long long n, long long r, long long p,long long fac[])
{
  //same code as above
}

int main()
{
    long long  fac[2001];
    fac[0] = 1;
    for (long long  i=1 ; i<=2000; i++)  //calculating factorials upto 2000
        fac[i] = fac[i-1]*i%M;
    for(i=0;i<2000;i++)
        nCrModPFermat(2000,i,M,fac);
}

My outputs where not as expected. Strangely, when I declared the fac[] array globally and calculated the factorials upto 2000 by calling a function:

long long  fac[2001];
void funci()
{
    fac[0] = 1;
    for (long long  i=1 ; i<=2000; i++)  //calculating factorials upto 2000
        fac[i] = fac[i-1]*i%M;
}

long long nCrModPFermat(long long n, long long r, long long p)
{
    //same code as above
}

int main()
{
    funci();
    for(i=0;i<2000;i++)
        nCrModPFermat(5000,i,M); 
}

I got the expected outputs. I just want to know why passing the array caused an error in the code

0

There are 0 best solutions below