You are not logged in. Please login at to post your questions!


How to solve a such problem based on fiboncci ?

A function is defined as follows :



GF(A,B,N)= GF(A,B,N-1)+GF(A,B,N-2) where N>1

Given 3 non negative numbers A B N returns remainder from division by 1000000007

For example given A =3 B=4 n =5 the function should return 29 BECAUSE

GF(3,4,0)= 3 mod 1000000007 = 3

GF(3,4,1)= 4 mod 1000000007 = 4

GF(3,4,2)= (GF(3,4,0)+GF(3,4,1)) mod 1000000007 =7

GF(3,4,3)= (GF(3,4,1)+GF(3,4,2)) mod 1000000007 =11

GF(3,4,4)= (GF(3,4,2)+GF(3,4,3)) mod 1000000007 =18

GF(3,4,5)= (GF(3,4,3)+GF(3,4,4)) mod 1000000007 =29

Can anyone solve this question in

time complexity: O(logN)

space complexity: O(1)

asked 09 Sep '16, 01:12

saksham458's gravatar image

accept rate: 50%

edited 10 Sep '16, 21:31

For finding the nth fibonacci number, you can use matrix exponentiation.

See code at


answered 10 Sep '16, 02:32

akshit_96's gravatar image

accept rate: 54%


Can you please code it I am facing issue with overflow.

or this is my code

if you can fix integer overflow in it. This code is not able to calculate it for big numbers.

It would be a great help.

(10 Sep '16, 07:37) saksham4580★

For getting a very fast implementation of only fibonacci numbers, you can refer to this thread :

BTW, I have a even smaller implementation for fibonacci numbers and according to the FIB64 problem on Spoj, I was ranked 14 among some of the fastest solution. You can find my implementation at

It works for all types on input and also handles the case even if we are multiplying even 2 "long long " values as well. The complexity is O(logn) and space complexity is O(1). Also, since mod operations are costly, the code has been designed in such a way so as to carry out mod operations only when required.

Hope it helps now.


answered 11 Sep '16, 15:32

likecs's gravatar image

accept rate: 9%

I think the question is already answered by @spinovations.

(12 Sep '16, 13:49) likecs6★

Can you explain what does mulmod function do?

(13 Sep '16, 00:04) error_503_4043★
(13 Sep '16, 15:20) likecs6★

If we observe the given function, we can see a pattern
G(a, b, 0) = a G(a, b, 1) = b G(a, b, 2) = a + b G(a, b, 3) = a + 2b G(a, b, 4) = 2a + 3b G(a, b, 5) = 3a + 5b G(a, b, 6) = 5a + 8b G(a, b, 7) = 8a + 13b
... and so on.

So if we consider the Fibonacci series as 0,1,1,2,3,5,8,13... with F(0) = 0, then

G(A, B, N) = A for N = 0 = F(N-1)*A + F(N)*B for all N > 0

It is possible to calculate F(N) in O(log N). The math is explained here.
The algorithm for the same can be found here (see Method 5 and 6).

All that is left is to evaluate the expression properly modulo 109+7.

Hope this helps :)


answered 09 Sep '16, 03:06

meooow's gravatar image

6★meooow ♦
accept rate: 49%


can you provide source code.

(09 Sep '16, 23:06) saksham4580★

@meooow @likecs @spinovations @slimtashady

This is my code

if you can fix integer overflow in it. This code is not able to calculate it for too big values.

It would be a great help.

(10 Sep '16, 07:37) saksham4580★

@saksham458 You are facing overflow because of lines such as these
int x = ((F[0][0]*M[0][0])%MOD + (F[0][1]*M[1][0])%MOD)%MOD;

It overflows when you do ((int)*(int)), so taking modulo of the wrong result does not help. You need to do this
int x = (int)((((long)F[0][0]*M[0][0])%MOD + ((long)F[0][1]*M[1][0])%MOD)%MOD);
so that the type is first promoted to long and then the expression is evaluated... or simply change the type of F and M arrays to long.

(10 Sep '16, 18:02) meooow ♦6★


why do we need to cast values to long?

(10 Sep '16, 18:25) saksham4580★

@meooow is there any technique for further optimazation.

It's taking too log for the inputs

A=2147483647 A=2147483647 N=1000000000

(10 Sep '16, 18:26) saksham4580★

Your code is taking too long for N=1000000000 because you are using a method of complexity O(n). Please pay attention my comment as well as the others who have commented. We clearly mention that Fibonacci should be calculated with O(log n) complexity and we have provided relevant links for that.

(11 Sep '16, 23:29) meooow ♦6★
showing 5 of 6 show all

Good code provided in comment no 2


answered 11 Sep '16, 22:46

rbpt's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 09 Sep '16, 01:12

question was seen: 4,664 times

last updated: 13 Sep '16, 15:20