How to calculate the last Fibonacci digit?

Question

Java

Hello! I'm taking an online course on algorithms. At the end of the first part, you need to complete the task:

Programming task. Given a number n (1≤n≤107), you need to find the last digit of the n-th Fibonacci number.
As we remember, Fibonacci numbers grow very quickly, so when calculating them, you need to be careful with overflow. In this problem, however, this problem can be avoided, since we are only interested in the last digit of the Fibonacci number: if 0≤a,b≤9 are the last digits of the numbers Fi and Fi+1, respectively, then (a+b)mod10 is the last digit of the number Fi+2.

Here is my solution code:

spoiler

import java.util.*;

class Main {
    
    private static int[] f = new int[10000000];
    private static int count = 0;
        public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int x = scanner.nextInt();
    long a = F(x-1)%10;
    long b = F(x-2)%10;
    long c = (a+b)%10;
    System.out.println(c);
  }
    
    public static long F(int N){
        if(N<count)return f[N];
        if(N==0){ count = 1; return f[0]=0; }
        if(N==1){ count = 2; return f[1]=1; }
        return f[N]=(int)(F(N-1)+F(N-2));
    }
}

But this code is not accepted and gives an error:

spoiler

Failed test #1. Run time error:
Exception in thread "main" java.lang.StackOverflowError
at Main.F(main.java:20)
at Main.F(main.java:20)
at Main.F(main.java:20)
at Main.F(main.java:20)
at Main.F(main.java:20)
at Main.F(main.java:20)
at Main.F(main.java:20)
at Main.F(main.java:20)
at Main.F(main.java:20)
at Main.F(main.java:20)
at Main.F(main.java:20)
at Main.F(main.java:20)
at Main.F(main.java:20)
at Main.F(main.java:20)

As I understand it, I still overflowed my memory. Help, please, how to avoid this?

Answer 1

You incorrectly used the hint in the problem statement.
In this problem, optimization should be achieved due to the fact that you do not calculate fibonacci numbers at all, but only their last digits. In your solution, you calculate the fibonacci numbers completely (in the F function) and only then take modulo 10 at the very last step.
You should put modulo 10 inside the F function. Something like this:

public static long F(int N){
        if (N < count) return f[N];
        if (N == 0) {count = 1; return f[0] = 0; }
        if (N == 1) {count = 2; return f[1] = 1; }
        return f[N] = (F(N-1)+F(N-2)) % 10;
    }

(And of course, replace the recursion with a loop, as you have already been told)

Answer 2

Try using Binet's formula

Answer 3

You can take advantage of the fact that the last digits form a periodic sequence and write something like this:
a=N%5;
if(a>1) a--;
b=((N/5)%4*2+1)%5;
if(b==0) b=2;
a=(a*b)%5;
c=(N%3+1)/2;
return a+((a+c)%2)*5;
No loops and no overflows. Admittedly, I didn't really check.

Answer 4

Offtopic: Could you provide a link to the course?