CC2 - Editorial

PROBLEM LINK

RIHANNA AND FIBONNACI

DIFFICULTY

EASY

PROBLEM

If a and b are the first two Fibonacci numbers what will be the rth number.

EXPLANATION

To calculate the rth fibonnaci number we need to precompute using matrix multiplication.
Case 1:
If r=1 answer is a
If r=2 answer is b
Else
alt text
So we need to pre compute for every r.

2 Likes

But how to calculate the matrix^(r-2) without having an O® complexity?

But how to calculate the matrix^(r-2) without having an O® complexity?

@ghaieth you should precompute the matrix^r for every r.

1 Like

can a and b be any number between 0 to 1000000 ??
Or they should a Fibonacci number ??

How is that possible?

@sam1906 can be any numbers

//