Large FIbonacci Java Time Exceeded

Question

I'm stuck on a test case. The question requires to compute a large Fibonacci number in a given period of time. I have passed 8 cases out of 10 and stuck on 9.

Here is my Code:

import java.util.*;
import java.math.BigInteger;
public class LastNumberofFibo {




public static void main(String[] args) {
    Scanner sc  = new Scanner(System.in);
    BigInteger bi = sc.nextBigInteger();


    System.out.println(fib(bi));
}



public static BigInteger fib(BigInteger n) {
    BigInteger val=new BigInteger("10");
    int k = n.intValue();
    BigInteger ans = null;

    if(k == 0) {
        ans = new BigInteger("0");
    } else if(Math.abs(k) <= 2) {
        ans = new BigInteger("1");
    } else {
        BigInteger km1 = new BigInteger("1");
        BigInteger km2 = new BigInteger("1");

        for(int i = 3; i <= Math.abs(k); ++i) {
            ans = km1.add(km2);
            km2 = km1;
            km1 = ans;
        }
    }

    if(k<0 && k%2==0) { ans = ans.negate(); }
    return ans.mod(val);
}

}

After Submitting I get the following Time-out result.

I need help in making my code more efficient.

Feedback :

Failed case #9/10: time limit exceeded Input: 613455

Your output:

stderr:

(Time used: 3.26/1.50, memory used: 379953152/536870912.)

Please guide me.

Yours Sincerely, Vidit Shah

It looks like you're only trying to return the last digit of a big Fibonacci number. So why not do all the arithmetic in mod 10, using `int` or `short` instead of `BigInteger`? — Dawood ibn Kareem, Apr 11 '17 at 21:08
The other thing you can do is take advantage of the fact that the pattern of last digits repeats every 60 Fibonacci numbers - so you could use `n % 60` in place of `n` as your argument to `fib`. — Dawood ibn Kareem, Apr 11 '17 at 21:11
Not a duplicate, @PeterdeRivaz - here, OP is looking for an answer mod 10, which makes it an entirely different problem. — Dawood ibn Kareem, Apr 11 '17 at 22:17
Wow! Code is byte-for-byte identical to the marked dup. I don't know what that means, though... — Ken Y-N, Apr 12 '17 at 01:15
@DavidWallace Apologies: I hadn't spotted that the modulo makes your more elegant solution possible - I've reopened the question as requested. — Peter de Rivaz, Apr 12 '17 at 07:58
Hint: fibonacci numbers are related to the powers of the matrix ((0,1)(1,1)) — Adder, Apr 12 '17 at 08:06
I was getting curious. That question with the identical code that seemed not to be a dupe anyway is here: [Very Large Fibonacci in Java](http://stackoverflow.com/questions/29551608/very-large-fibonacci-in-java). — Ole V.V., Apr 12 '17 at 19:39

Adder · Accepted Answer · 2017-04-12T11:31:05.560

I have taken the most easy to implemement suggestions from comments and put it in code.

import java.util.*;
import java.math.BigInteger;
public class LastNumberofFibo {


    public static void main(String[] args) {
        Scanner sc  = new Scanner(System.in);
        BigInteger bi = sc.nextBigInteger();


        System.out.println(fib(bi));
    }


    public static BigInteger fib(BigInteger n) {
        int m = 10;
        BigInteger sixty = new BigInteger("60");
        int k = (n.mod(sixty)).intValue();
        int ans = 0;

        if(k == 0) {
            ans = 0;
        } else if(Math.abs(k) <= 2) {
            ans = 1;
        } else {
            int km1 = 1;
            int km2 = 1;

            for(int i = 3; i <= Math.abs(k); ++i) {
                ans = (km1 + km2)%m;
                km2 = km1;
                km1 = ans;
            }
        }

        if(k<0 && k%2==0) { ans = -ans; }
        return new BigInteger("" + ans);
    }

}

score 0 · Answer 2 · answered Feb 26 '21 at 16:24

0

Try that:

public static int fibonacci(int n) {
    return (int)((Math.pow((1 + Math.sqrt(5)) / 2, n) - Math.pow((1 - Math.sqrt(5)) / 2, n)) / Math.sqrt(5));
}

answered Feb 26 '21 at 16:24

Borislav Markov

1,495
11
12

Large FIbonacci Java Time Exceeded

2 Answers2