Fibonacci Sum of Large Numbers(Only Last Digit to be Printed)

SOLVED IT

Works on all range of inputs. It works on the following algorithm. The idea is to notice that the last digits of fibonacci numbers also occur in sequences of length 60 (from the previous problem: since pisano peiod of 10 is 60). Irrespective of how large n is, its last digit is going to have appeared somewhere within the sequence. Two Things apart from edge case of 10 as last digit.

• Sum of nth Fibonacci series = F(n+2) -1
• Then pisano period of module 10 = let n+2 mod (60) = m then find F(m) mod(10)-1

Code as follows;

#include <iostream>
using namespace std;

long long calc_fib(long long n) {

    n = (n+2)%60;
    int fib[n+1];
    fib[0]=0;
    fib[1]=1;
    int res = 1;
    for(int i = 2; i<=n;i++){
        fib[i] = (fib[i-1]%10 + fib[i-2]%10)%10;
        // res = res + fib[i];
    }
    // cout<<fib[n]<<"\n";
    if(fib[n] == 0){
        return 9;
    }
    return (fib[n]%10-1);
}

int main() {
    long long n = 0;
    std::cin >> n;

    std::cout << calc_fib(n) << '\n';
    return 0;
}

If you only need to output the last digit as you said, I think you can just make use of the Pisano Period you mentioned, as for modular 10, the cycle length is only 60 and you can just pre-make an array of that 60 digits.

If you want to compute by yourself, I think you can use Matrix Exponentiation which gives you O(lg N) complexity, when calculating the matrix exponents, keep storing the temporary result modular 10. See the Matrices section for your reference.

Actually it's even easier than Niall answer

int get_fibonacci_sum_last_digit(long long n) {
    const int kPisanoSize = 60;
    int rest = n % kPisanoSize;
    int preparedNumbers[kPisanoSize] = {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};
    return preparedNumbers[rest];

}