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

Question

I have been trying to come out with a solution regarding the problem of finding the last digit of the sum of large n Fibonacci series. I have been able to pass several test cases with large n. But I'm stuck at the following case where n = 832564823476. I know it can be solved using Pisano's period but I'm unable to come out with a efficient algo. Any help would be great. Thanks. My code that I have implemented is as follows-

#include <iostream>
using namespace std;


int calc_fib(int n) {

    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];
    }
    return (res%10);
}

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

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

Answer 1

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;
}