## Wednesday, July 27, 2016

### Program to find last digit of n'th Fibonnaci Number - GeeksforGeeks

Program to find last digit of n'th Fibonnaci Number - GeeksforGeeks
Given a number 'n', write a function that prints the last digit of n'th ('n' can also be a large number) Fibonacci number.
Look at the final digit in each Fibonacci number – the units digit:
```0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...
```
Is there a pattern in the final digits?
```0, 1, 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, ...

```
Yes!
It takes a while before it is noticeable. In fact, the series is just 60 numbers long and then it repeats the same sequence again and again all the way through the Fibonacci series – for ever. The series of final digits repeats with a cycle length of 60 (Refer this for explanations of this result).
`    ``void` `fib(``int` `f[])`
`    ``{`
`        ``/* 0th and 1st number of the series are 0 and 1*/`
`        ``f[``0``] = ``0``;`
`        ``f[``1``] = ``1``;`

`        ``/* Add the previous 2 numbers in the series`
`           ``and store last digit of result */`
`        ``for` `(``int` `i = ``2``; i <= ``59``; i++)`
`            ``f[i] = (f[i-``1``] + f[i-``2``])%``10``;`
`    ``}`

`    ``// Returns last digit of n'th Fibonacci Number`
`    ``int` `findLastDigit(``long` `n)`
`    ``{`
`        ``// In Java, values are 0 by default`
`        ``int` `f[] = ``new` `int``[``60``];`

`        ``// Precomputing units digit of first 60`
`        ``// Fibonacci numbers`
`        ``fib(f);`
`   `
`        ``int` `index = (``int``)(n % 60L); `
` `
`        ``return` `f[index];`
`    ``}`

Simple approach is to calculate the n’th Fibonacci number and printing the last digit.
`    ``static` `long` `fib(``long` `n)`
`    ``{`
`        ``long` `F[][] = ``new` `long``[][] {{``1``,``1``},{``1``,``0``}};`
`        ``if` `(n == ``0``)`
`            ``return` `0``;`
`        ``power(F, n-``1``);`

`        ``return` `F[``0``][``0``];`
`    ``}`

`    ``// Utility function to multiply two matrices and`
`    ``// store result in first.`
`    ``static` `void` `multiply(``long` `F[][], ``long` `M[][])`
`    ``{`
`        ``long` `x =  F[``0``][``0``]*M[``0``][``0``] + F[``0``][``1``]*M[``1``][``0``];`
`        ``long` `y =  F[``0``][``0``]*M[``0``][``1``] + F[``0``][``1``]*M[``1``][``1``];`
`        ``long` `z =  F[``1``][``0``]*M[``0``][``0``] + F[``1``][``1``]*M[``1``][``0``];`
`        ``long` `w =  F[``1``][``0``]*M[``0``][``1``] + F[``1``][``1``]*M[``1``][``1``];`

`        ``F[``0``][``0``] = x;`
`        ``F[``0``][``1``] = y;`
`        ``F[``1``][``0``] = z;`
`        ``F[``1``][``1``] = w;`
`    ``}`

`    ``/* Optimized version of power() in method 4 */`
`    ``static` `void` `power(``long` `F[][], ``long` `n)`
`    ``{`
`        ``if``( n == ``0` `|| n == ``1``)`
`            ``return``;`
`        ``long` `M[][] = ``new` `long``[][] {{``1``,``1``},{``1``,``0``}};`

`        ``power(F, n/``2``);`
`        ``multiply(F, F);`

`        ``if` `(n%``2` `!= ``0``)`
`            ``multiply(F, M);`
`    ``}`

`    ``// Returns last digit of n'th Fibonacci Number`
`    ``long` `findLastDigit(``long` `n)`
`    ``{`
`        ``return` `(fib(n) % ``10``);`
`    ``}`