Given a number ‘n’, write a function that prints the last digit of n’th (‘n’ can also be a large number) Fibonacci number.
Examples :
Input : n = 0
Output : 0
Input: n = 2
Output : 1
Input : n = 7
Output : 3
Method 1 : (Naive Method)
Simple approach is to calculate the n’th Fibonacci number and printing the last digit.
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
void multiply(ll F[2][2], ll M[2][2]);
void power(ll F[2][2], ll n);
ll fib( int n)
{
ll F[2][2] = {{1, 1}, {1, 0}};
if (n == 0)
return 0;
power(F, n - 1);
return F[0][0];
}
void power(ll F[2][2], ll n)
{
if (n == 0 || n == 1)
return ;
ll M[2][2] = {{1, 1}, {1, 0}};
power(F, n / 2);
multiply(F, F);
if (n % 2 != 0)
multiply(F, M);
}
void multiply(ll F[2][2], ll M[2][2])
{
ll x = F[0][0] * M[0][0] +
F[0][1] * M[1][0];
ll y = F[0][0] * M[0][1] +
F[0][1] * M[1][1];
ll z = F[1][0] * M[0][0] +
F[1][1] * M[1][0];
ll 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;
}
int findLastDigit( int n)
{
return fib(n) % 10;
}
int main()
{
ll n = 1;
cout << findLastDigit(n) << endl;
n = 61;
cout << findLastDigit(n) << endl;
n = 7;
cout << findLastDigit(n) << endl;
n = 67;
cout << findLastDigit(n) << endl;
return 0;
}
|
Java
class GFG
{
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 ];
}
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;
}
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);
}
long findLastDigit( long n)
{
return (fib(n) % 10 );
}
public static void main(String[] args)
{
int n;
GFG ob = new GFG();
n = 1 ;
System.out.println(ob.findLastDigit(n));
n = 61 ;
System.out.println(ob.findLastDigit(n));
n = 7 ;
System.out.println(ob.findLastDigit(n));
n = 67 ;
System.out.println(ob.findLastDigit(n));
}
}
|
Python3
def fib(n):
F = [[ 1 , 1 ], [ 1 , 0 ]];
if (n = = 0 ):
return 0 ;
power(F, n - 1 );
return F[ 0 ][ 0 ];
def multiply(F, M):
x = F[ 0 ][ 0 ] * M[ 0 ][ 0 ] + F[ 0 ][ 1 ] * M[ 1 ][ 0 ];
y = F[ 0 ][ 0 ] * M[ 0 ][ 1 ] + F[ 0 ][ 1 ] * M[ 1 ][ 1 ];
z = F[ 1 ][ 0 ] * M[ 0 ][ 0 ] + F[ 1 ][ 1 ] * M[ 1 ][ 0 ];
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;
def power(F, n):
if ( n = = 0 or n = = 1 ):
return ;
M = [[ 1 , 1 ], [ 1 , 0 ]];
power(F, int (n / 2 ));
multiply(F, F);
if (n % 2 ! = 0 ):
multiply(F, M);
def findLastDigit(n):
return (fib(n) % 10 );
n = 1 ;
print (findLastDigit(n));
n = 61 ;
print (findLastDigit(n));
n = 7 ;
print (findLastDigit(n));
n = 67 ;
print (findLastDigit(n));
|
C#
using System;
class GFG
{
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];
}
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;
}
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);
}
static long findLastDigit( long n)
{
return (fib(n) % 10);
}
public static void Main()
{
int n;
n = 1;
Console.WriteLine(findLastDigit(n));
n = 61;
Console.WriteLine(findLastDigit(n));
n = 7;
Console.WriteLine(findLastDigit(n));
n = 67;
Console.WriteLine(findLastDigit(n));
}
}
|
PHP
<?php
function fib( $n )
{
$F = array ( array (1, 1),
array (1, 0));
if ( $n == 0)
return 0;
power( $F , $n - 1);
return $F [0][0];
}
function multiply(& $F , & $M )
{
$x = $F [0][0] * $M [0][0] +
$F [0][1] * $M [1][0];
$y = $F [0][0] * $M [0][1] +
$F [0][1] * $M [1][1];
$z = $F [1][0] * $M [0][0] +
$F [1][1] * $M [1][0];
$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 ;
}
function power(& $F , $n )
{
if ( $n == 0 || $n == 1)
return ;
$M = array ( array (1, 1), array (1, 0));
power( $F , (int)( $n / 2));
multiply( $F , $F );
if ( $n % 2 != 0)
multiply( $F , $M );
}
function findLastDigit( $n )
{
return (fib( $n ) % 10);
}
$n = 1;
echo findLastDigit( $n ) . "\n" ;
$n = 61;
echo findLastDigit( $n ) . "\n" ;
$n = 7;
echo findLastDigit( $n ) . "\n" ;
$n = 67;
echo findLastDigit( $n ) . "\n" ;
|
Javascript
<script>
function fib(n)
{
let F = [[1, 1], [1, 0]];
if (n == 0)
return 0;
power(F, n - 1);
return F[0][0];
}
function multiply(F, M)
{
let x = F[0][0] * M[0][0] +
F[0][1] * M[1][0];
let y = F[0][0] * M[0][1] +
F[0][1] * M[1][1];
let z = F[1][0] * M[0][0] +
F[1][1] * M[1][0];
let 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;
}
function power(F, n)
{
if ( n == 0 || n == 1)
return ;
let M = [[1, 1], [1, 0]];
power(F, parseInt(n / 2, 10));
multiply(F, F);
if (n % 2 != 0)
multiply(F, M);
}
function findLastDigit(n)
{
return (fib(n) % 10);
}
let n;
n = 1;
document.write(findLastDigit(n) + "</br>" );
n = 61;
document.write(findLastDigit(n) + "</br>" );
n = 7;
document.write(findLastDigit(n) + "</br>" );
n = 67;
document.write(findLastDigit(n));
</script>
|
Complexity: O(Log n).
Limitation of this implementation:
Fibonacci numbers grow exponentially fast. For example, the 200’th Fibonacci number equals 280571172992510140037611932413038677189525. And F(1000) does not fit into the standard C++ int type.
To overcome this difficulty, instead of calculating n’th Fibonacci number, there is a direct algorithm to just calculate its last digit (that is, F(n) mod 10).
Method 2 : (Direct Method)
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).
So, instead of calculating the Fibonacci number again and again, pre-compute the units digit of first 60 Fibonacci number and store it in an array and use that array values for further calculations.
C++
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll fib(ll f[], ll n)
{
f[0] = 0;
f[1] = 1;
for (ll i = 2; i <= n; i++)
f[i] = (f[i - 1] + f[i - 2]) % 10;
return f[n];
}
int findLastDigit( int n)
{
ll f[60] = {0};
fib(f, 60);
return f[n % 60];
}
int main ()
{
ll n = 1;
cout << findLastDigit(n) << endl;
n = 61;
cout << findLastDigit(n) << endl;
n = 7;
cout << findLastDigit(n) << endl;
n = 67;
cout << findLastDigit(n) << endl;
return 0;
}
|
Java
class GFG
{
void fib( int f[])
{
f[ 0 ] = 0 ;
f[ 1 ] = 1 ;
for ( int i = 2 ; i <= 59 ; i++)
f[i] = (f[i - 1 ] + f[i - 2 ]) % 10 ;
}
int findLastDigit( long n)
{
int f[] = new int [ 60 ];
fib(f);
int index = ( int )(n % 60L);
return f[index];
}
public static void main(String[] args)
{
long n;
GFG ob = new GFG();
n = 1 ;
System.out.println(ob.findLastDigit(n));
n = 61 ;
System.out.println(ob.findLastDigit(n));
n = 7 ;
System.out.println(ob.findLastDigit(n));
n = 67 ;
System.out.println(ob.findLastDigit(n));
}
}
|
Python3
def fib(f, n):
f[ 0 ] = 0 ;
f[ 1 ] = 1 ;
for i in range ( 2 , n + 1 ):
f[i] = (f[i - 1 ] + f[i - 2 ]) % 10 ;
return f;
def findLastDigit(n):
f = [ 0 ] * 61 ;
f = fib(f, 60 );
return f[n % 60 ];
n = 1 ;
print (findLastDigit(n));
n = 61 ;
print (findLastDigit(n));
n = 7 ;
print (findLastDigit(n));
n = 67 ;
print (findLastDigit(n));
|
C#
using System;
class GFG {
static void fib( int []f)
{
f[0] = 0;
f[1] = 1;
for ( int i = 2; i <= 59; i++)
f[i] = (f[i - 1] + f[i - 2]) % 10;
}
static int findLastDigit( long n)
{
int []f = new int [60];
fib(f);
int index = ( int )(n % 60L);
return f[index];
}
public static void Main()
{
long n;
n = 1;
Console.WriteLine(findLastDigit(n));
n = 61;
Console.WriteLine(findLastDigit(n));
n = 7;
Console.WriteLine(findLastDigit(n));
n = 67;
Console.WriteLine(findLastDigit(n));
}
}
|
PHP
<?php
function fib(& $f , $n )
{
$f [0] = 0;
$f [1] = 1;
for ( $i = 2; $i <= $n ; $i ++)
$f [ $i ] = ( $f [ $i - 1] +
$f [ $i - 2]) % 10;
return $f [ $n ];
}
function findLastDigit( $n )
{
$f = array_fill (0, 60, 0);
fib( $f , 60);
return $f [ $n % 60];
}
$n = 1;
print (findLastDigit( $n ) . "\n" );
$n = 61;
print (findLastDigit( $n ) . "\n" );
$n = 7;
print (findLastDigit( $n ) . "\n" );
$n = 67;
print (findLastDigit( $n ) . "\n" );
?>
|
Javascript
<script>
function fib(f)
{
f[0] = 0;
f[1] = 1;
for (let i = 2; i <= 59; i++)
f[i] = (f[i - 1] + f[i - 2]) % 10;
}
function findLastDigit(n)
{
let f = new Array(60);
f.fill(0);
fib(f);
let index = (n % 60);
return f[index];
}
let n;
n = 1;
document.write(findLastDigit(n) + "</br>" );
n = 61;
document.write(findLastDigit(n) + "</br>" );
n = 7;
document.write(findLastDigit(n) + "</br>" );
n = 67;
document.write(findLastDigit(n) + "</br>" );
</script>
|