What's wrong with my code for FIBOSUM?

#1

Question link : https://hack.codingblocks.com/app/practice/3/227/problem

My solution link : https://ide.codingblocks.com/s/282068

#2

hello @priyamthakuria27
ur solution is brute force , it will not work because constraint are large.

use matrix exponentiation to pass all test case.

refer this->
this problem, obviously, you can’t just iterate through numbers from f(n) to f(m), this will TLE, so you have to think of something new.

usually when you are asked to sum (or anything else) the numbers from a to b, the solution would be in getting the formula of the sum from 0 to x, and then the answer is simply: sum(b)-sum(a-1)

at first try to write the first few fibo numbers:
0 1 1 2 3 5 8 13 21 34 55

now write the sum of fibo numbers from 0 to i:
0 1 2 4 7 12 20 33 54

look for a pattern in these numbers. Do you see it?!!

note that sum(x) = fib(x+2)-1

now, x still may be up to 10^9, and it can’t be calculated naively.
Lucky us, there is a faster way to calculate fibonacci numbers, using matrix powers.

image

you can calculate this using fast matrix exponentiation and you’ll get yourself a neat O(log n) solution.

#3

I didn’t quite understand.
Can you give me the solution?

#4

bro read about matrix exponentiation.
then only u will be able to solve this problem

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.