CC2 - Editorial

editorial
, , ,
1

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
2

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

3

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

4

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

1 Like
5

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

6

How is that possible?

7

@sam1906 can be any numbers