0

I am try to solve a question https://practice.geeksforgeeks.org/problems/nth-catalan-number/0 by using the approach where k =n -r

for(int i=0; i<k; i++){
                        res = res * (n - i);
                        res = (res/(i+1))%1000000007;
                    }
for n and r
but it get failed in the input n=778  and r = 116
but using the dynamic programming (by using two dimensional array) method it give the right answer
what are the reason of failure of first approach and success of second (dynamic programming) approach
aniket aniket
  • 77
  • 2
  • 7

1 Answers1

0
(a / b) mod p = ((a mod p) * (b^(-1) mod p)) mod p

You should use modular division.

Look at this question Link

Setonix
  • 205
  • 2
  • 13