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);

    }

Read full article from Program to find last digit of n'th Fibonnaci Number - GeeksforGeeks