Coursera: Calculating sum of numbers in the fibonacci sequence between two specific points in the series Question

This is an assignment for a Coursera course.



This is the algorithm I wrote.

import java.util.*;

public class FibonacciPartialSum {
    private static long getFibonacciPartialSumNaive(long from, long to) {
        if (to &lt;= 1)
            return to;

        long prev = 0;
        long cur = 1;
        long sum;

        if(from == 1) {
            sum = 1;
        }
        else {
            sum = 0;
        }

        for (long i = 2; i &lt;= to; i++) {
            long temp_prev = prev;
            prev = cur;
            cur = (cur + temp_prev) % 10;

            if (i &gt;= from) {
                sum = (sum + cur) % 10;
            }

        }
        return sum;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long from = scanner.nextLong();
        long to = scanner.nextLong();
        //long from = 1234;
        //long to = 12345;
        System.out.println(getFibonacciPartialSumNaive(from, to));
        scanner.close();
    }
}


When I submit it to auto grader in Coursera it states that I failed the time test.


Failed case #8/12: time limit exceeded Input: 1 10000000000

Your output:

stderr:

(Time used: 3.03/1.50, memory used: 26427392/536870912.)
Runtime improvement

If you take a look at the last digit of the first few fibonacci numbers you will see that the digits are repeated after 60 numbers. As the digits in this range have a sum of 0 you can calculate the sum for [from%60,to%60] instead.

Bug

The task states that the given integer are non-negative, 0 is a valid value. Currently you are returning i.e. 1 for the range [0,2] as 0 is treated as 2, the initialization of sum has to be changed to:

if (from &lt;= 1) {
    sum = 1;
} else {
    sum = 0;
}


(I would initialize sum with a ternary operator long sum = from &lt;= 1 ? 1 : 0 instead.)

Types

As the values of sum, prev and cur are always in the range [0,10), you can use int instead of long for these variables, int arithmetic is likely to be faster than long arithmetic.

Alternative implementation

The remaining range is quite small -> you could cache the results for every number in the range [0,60) to avoid calculating the sum on each invocation.

private static final byte[] DIGIT_SUM = {
        0, 1, 2, 4, 7, 2, 0, 3, 4, 8,
        3, 2, 6, 9, 6, 6, 3, 0, 4, 5,
        0, 6, 7, 4, 2, 7, 0, 8, 9, 8,
        8, 7, 6, 4, 1, 6, 8, 5, 4, 0,
        5, 6, 2, 9, 2, 2, 5, 8, 4, 3,
        8, 2, 1, 4, 6, 1, 8, 0, 9, 0};

private static int fibonacciPartialSum(long m, long n) {
    assert m &lt;= n &amp; (m | n) &gt;= 0;
    int v = fibSumLastDigit(n);
    return m == 0 ? v : (v -= fibSumLastDigit(m - 1)) + (10 &amp; v &gt;&gt; -1);
}

private static int fibSumLastDigit(long n) {
    return DIGIT_SUM[(int) (n % 60)];
}