Sum of last digits of large fibonacci numbers upto nth term

[fishysun]

Hello everyone. I was trying to solve the problem stated in the title, but my algorithm was a naive one and it didn’t display the correct outputs. I found out a solution on stack overflow, but I wasn’t able to understand the code .I know that the Pissano period property of Fibonacci numbers is being used here but still it confuses me. Can anyone please help me to understand the code:

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

Thanks in advance

[simes]

I couldn’t find the problem, can you provide a link to it?

[fishysun]

It is actually given in an assignment in EdX. So you can’t see the problem unless you sign in with an account.But I will attach a screenshot of the problem.

Here is what I get to see.

[rajan9519]

@fishysun
If you write piassano series of fibonacci number mode 10 you will find that the period is 60.
Now try to find the pattern in sum of n fibonacci numbers.
When you do so you will see that S(n) = F(n+2) - 1
S denotes some of n fibonacci numbers and F(n) denotes n’th fibonacci number.
Now your work is to find the (F(n+2)-1)%10 for sum of n fibonacci numbers, and you know that period is 60 so you can replace n+2 by (n+2)%60 and that piassano series number will give you the F(n+2)%10.
Also take care of -1 term for finding mode.

[fishysun]

@rajan9519 is that why in the program we return a 9 when the fib[n] == 0 so that we don’t get a -1?. I understood all the other points you mentioned and thanks, that explanation really made it simple

[rajan9519]

is that why in the program we return a 9 when the fib[n] == 0 so that we don’t get a -1?

Yes.

[fishysun]

@rajan9519
Thanks man!