how to find the sum of n fibonacci numbers so that time limit does not exceed?

where n <=10^18

Yes, check hc notes. And their code. Its the fastest code on the internet to calculate nth-fibonacci number.

During a HMC contest, I tried 16-17 different possible codes from various places on internet to calculate nth-fibonacci number and the one I mentioned above gave AC, rest all TLE,even the code in above link did not work as TL was too strict

yeah i have used in contest also for bruteforces solution.

btw what is this HMC contest

here is all approach

well here i am not talkin about nth term coz u have to take the exponentiation of a certain matrix .

i am talking about sum of n terms where n can be 10^18.Will this method wont be TLE?

Hello @phoenix0203

If you fiddle around with the expression of sum of n Fibonacci numbers, you will be able to express the sum of n fibonacci numbers as {fib(n+2) - 1}.

So the sum of first n fibonacci numbers S(n) can be written as

S(n) = fib(n+2) - 1;

Now i leave to you the question as to, why we can solve this in matrix exponentiation without breaching acceptable time limits.

Tread Carefully, Hints below

Hint1 : You can do this with a 2x2 matrix.

Hint2 : (A^x) for any integer x in can be done in O((n^3) * log2x), where A is the matrix and n is the dimension of matrix.

Happy Coding.

Hello @anon55659401

Can you please clarify what you mean by âhc notesâ and âHMC contestâ?

I am unable to deduce it.

Thank You

You can do it in o(1)

Nth Fibonacci no in given by

Fn = {[(â5 + 1)/2] ^ n} / â5

Itâs a simple gp now

Use big integer in java to process in one go

Hope it helps

Hello @avenger786

I am aware of this approach. But first you have to reach S(n) = fib(n+2) -1 to apply that formula.

Use BigInteger.It might help

I think what you are looking for is matrix exponentiation.

Never use this, it does not give accurate results cuz of square root and divide operations, use matrix exponentiation which works in O(lgN) time.

https://www.geeksforgeeks.org/sum-fibonacci-numbers/ Read this, I donât have the time to explain the basic property of fibonacci numbers in detailâŚ