Last Digit of the Sum of Fibonacci Numbers in range a to b

Question

my solution is failing the test case 1234 12345 in the output and it is giving output 2 instead of correct output 8 although some of the test cases in the question sample have passed . please point out my mistake. thank you.


#include <bits/stdc++.h>

using namespace std;

int calc_fib(long long n) {
    long long int m, o = 0, p = 1, q = 1;
    m = (n+2) % 60;

    for(long long int i = 2 ; i <= m ; i++) {
        q = o + p;
        o = p;
        p = q;
    }

    //if m=0 then q should be 0 and not 1 so base case
    if(m == 0) q = 0;

    return q;
}

int main() {
    long long a, b;
    cin>>a>>b;

    int result1 = calc_fib(b);
    int result2 = calc_fib(a-1);
    int final_result = ((result1%10) - (result2%10) + 10) % 10;

    cout<<final_result;
    return 0;
}

If you are doing `calc_fib(b)` anyway, you can just collect the result in a separate variable when `i` reaches `a` and on wards. This way, you can avoid `calc_fib(a-1);` — nice_dev, Jun 10 '20 at 14:58
https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h — Yunnosch, Jun 10 '20 at 15:07
Yes thank you @vivek_23 for that comment. Collecting the result and storing in a separate variable is a better way to do it. Thanks. I have shared the image of the question as well now. — Aanchal Chaurasia, Jun 11 '20 at 14:41
It's from a course I've doing from Coursera so the link can't be shared. Only if you enrol for the course you'll be able to see the assignment questions. :/ — Aanchal Chaurasia, Jun 12 '20 at 11:18

nice_dev · Accepted Answer · 2020-06-12T04:49:11.970

If you are doing calc_fib(b) anyway, you can just collect the result in a separate variable when i reaches a and on wards. This way, you can avoid calc_fib(a-1);

If this is for a single range of a to b, you can compute on the fly, else precompute them by caching them in an array and just do calc_fib(b) - calc_fib(a-1).

You are doing

    q = o + p;
    o = p;
    p = q;

This will lead to integer overflow since fibonacci numbers can become large after 20^th or so.

Find last digit of sum of all fibonacci from a to b is equivalent to just sum all last digits of each fibonacci from ath term to bth term. So, you can just keep MODing it by 10, both for sum as well as the numbers.

#include <bits/stdc++.h> // use any other alternative for this as it doesn't seem to be a good practice

using namespace std;

int calc_fib(long long a,long long b) {
    if(b <= 2) return b;
    int prev = 1,curr = 1,sum = a < 3 ? 2 : 0;
    long long int i = 1;
    for(i = 3; i <= b; ++i){
        curr += prev;
        prev = curr - prev;
        if(i >= a){
            sum = (sum + curr) % 10;
        }       
        prev %= 10;
        curr %= 10;
    }

    return sum;
}

int main() {
    long long a = 0, b = 0;
    cin>>a>>b;
    cout<<calc_fib(a,b);
    return 0;
}

Thank you @vivek_23 . This was really helpful and detailed answer. Thanks a lot! — Aanchal Chaurasia, Jul 05 '20 at 10:57

Last Digit of the Sum of Fibonacci Numbers in range a to b

1 Answers1