Last Digit of a Large Fibonacci Number fast algorithm

  • A+
Category:Languages

I'm trying to solve Fibonacci using java, but my code takes so long with big numbers.

Problem Description Task. Given an integer 𝑛, find the last digit of the 𝑛th Fibonacci number 𝐹𝑛 (that is, 𝐹𝑛 mod 10).

Input Format. The input consists of a single integer 𝑛.

Constraints. 0 ≤ 𝑛 ≤ 10⁷.

Output Format. Output the last digit of 𝐹𝑛.

My code:

public class FibonacciLastDigit {  private static int getFibonacciLastDigitNaive(int n) {     if (n <= 1) {         return n;     }     BigInteger first = BigInteger.ZERO;     BigInteger second = BigInteger.ONE;     BigInteger temp;      for (int i = 1; i < n; i++) {         temp = first.add(second);         first = second;         second = temp;     }     return second.mod(BigInteger.TEN).intValue(); }  public static void main(String[] args) {     Scanner scanner = new Scanner(System.in);     int n = scanner.nextInt();     System.out.println(getFibonacciLastDigitNaive(n)); }} 

My code fails if input = 613455 it takes 30 seconds to get value and max allowed time is 1.5 second.

I had to use big Integer because long isn't enough.

 


Your implementation is indeed naive, because you're asked to get the last digit of the Fibonacci number not the actual Fibonacci number itself. You only need to keep the track of the last digit, other digits don't matter.

public static void main(String[] args) {     Scanner scanner = new Scanner(System.in);     int n = scanner.nextInt();     System.out.println(getFibonacciLastDigit(n)); }  private static int getFibonacciLastDigit(int n) {     if (n <= 1) {         return n;     }     int first = 0;     int second = 1;     int temp;      for (int i = 1; i < n; i++) {         temp = (first + second) % 10;         first = second;         second = temp;     }     return second; } 

Comment

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: