Please Help to find nCr

I need to find sum of first k term of nCr when n is in fibonaccci and r is constant.

for eg. 2C2 + 3C2 + 5C2 + 8C2 + . . . . . (till Kth term). where k is given.

The maximum value of k can be until 10^18 so loop will not work. any formula or O(logn) complexity algorithm will only work.

Can anyone please help. @vijju123 @waqar_ahmad224 @taran_1407 @galencolin @carre

1 Like

I’m assuming r=2, and r cannot go beyond 2 since according to your example, fibonacci starts from 2.

Take a=2, b=3, sum=a*(a-1) + b*(b-1)

From i=3 to k{
c=a+b
sum+= c*(c-1)
a=b
b=c
}

Print sum/2

Logic: nC2 = n*(n-1)/2

The maximum value of k can be until 10^18 so loop will not work. any formula or O(logn) complexity algorithm will only work.

Okay. You should’ve provided the constraints along with the question…