C(n, k) = n ! / (n-k) ! k! = n (n-1) ... (n-k+1) / 1. 2. ... (k-1)k
C(n,k) = C(n, n-k) = n! / (n-n +k)! (n-k)! so we can change r to r-p is r > p-r and keep the operation smaller
for (i = 0; i < k; i++)
{
res *= (n - i);
res /= (i+1);
}
O(k) time and (1) space
No comments:
Post a Comment