0

I had the doubt in finding the last digit of sum of terms of fibonacci series ranging from index m to index n(Consider starting term to have index 0).

I have lots of different ways to solve the problem. But it is required to pass very long cases as well for ex m=2,n=82364572389 etc. But when I tried with this algorithm, mine some test cases were passed but some didn't.

S can you help me out that is there any problem in my Code or is this Algorithm wrong.

Also how to do this Problem with better approach.

#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,m;

std::cin >> m;

    std::cin >> n;

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

Test cases

Test Case: 5 10
Correct Output: 6
My Output: -4

Test Case: 1 10000000
Correct Output: 5
My Output: 5
Stefan Becker
  • 5,695
  • 9
  • 20
  • 30
Kushal Dev
  • 1
  • 1
  • 3
  • 3
    `int fib[n+1];` is not valid C++. –  Sep 09 '19 at 15:41
  • `int fib[n+1];` is [undefined behavior](https://stackoverflow.com/questions/32132574/does-undefined-behavior-really-permit-anything-to-happen). –  Sep 09 '19 at 15:51
  • When you say last digit of the sum, you mean approximation by nth decimal or literally add every number in series ? – Danilo Sep 09 '19 at 16:06
  • 1
    You're computing the difference between the last digit of the n:th number and the last digit of the m-1:st number. That's not what the problem is. – molbdnilo Sep 09 '19 at 16:07
  • interesting way to approach this issue is to try to derive polynomial function from standard [summation formula](https://i.pinimg.com/originals/16/25/ce/1625ce7cfcdbdc19ab083e9be61dcf51.png) by stepping function of golden ratio with invert step for deviation. Have in mind that Fibonacci sequence is an idealisation of golden mean - so some integer magic needs to be implemented, and Fibonacci sequence heavily depends on its base. `Fib(3, item=4) != Fib(6, item =4) – Danilo Sep 09 '19 at 16:14
  • Where is the 60 from ? It seems like a very clever solution to a thougher problem than what the question asks – Jeffrey Sep 09 '19 at 17:09
  • No there is no problem with int fib[n+1]; – Kushal Dev Sep 10 '19 at 04:38
  • 60 is the Pisano Period for fb[i]mod10. – Kushal Dev Sep 10 '19 at 04:49

2 Answers2

0

You need to change your algorithms.

First thing: don't compute the values recursively. This is crazy expensive as far as run-time goes. Start with f(0), then f(1), then compute f(2) using the two last stored values. Continue this way. Store only the last two values.

Second: realize that there's no point storing f(n) fully. You can just keep the units and tens (the tens are not needed, but will help in debugging). This will look like: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 44, 33

Notice that 89+44 gives 133, which ends in 33, just like 89+144 gives 233, which also ends in 33.

Once you combine both, you'll need a single loop, with a counter going to say, 82364572389, and performs simple additions/modulos. It should end in minutes, top.

Once there, you can start thinking about further optimizations (there are). But the two above should be enough.

Also, from comments, and re-reading the question:

calc_fib(n) - calc_fib(m-1)

is wrong as it could yield a negative number. Whereas the last digit has to be positive. You probably need to take this difference diff, and do:

diff = (diff + 10) % 10;

to make it positive.

And lastly, why 9 ? and why -1 in return (fib[n]%10-1); ? this seems to offset everything by one, but both -1 in the subtraction cancels out.

Jeffrey
  • 11,063
  • 1
  • 21
  • 42
  • The question is about the sum of Fibonacci values from some start index to some end index. While all your remarks are useful, the one failing test case shown fails due to an unrelated reason. – Max Langhof Sep 09 '19 at 16:06
  • That's a good point. The n = (n+2)%60; bit hints at the OP knowing more than the question states. But then, the calc_fib(n) - calc_fib(m-1) is a blunder – Jeffrey Sep 09 '19 at 17:04
0

Keep moving the sum inside of the for loop, as below:

#include <iostream>
using namespace std;

int main() {
    unsigned int i, j, n, v, sum;

    cout << "Fibonacci numbers from 1 to 10000: " << endl;

    cout << '1' << endl;
    cout << '1' << endl;
    cout << '2' << endl;
    for (i = j = v = 1, n = 2, sum = 4; n + j < 10000; sum += v) {
        v = n + j; i = j; j = n; n = v;
        cout << v << endl;
    }

    cout << "Sum of Fibonacci numbers from 1 to 10000: " << sum << endl;

    return 0;
}

ADDED LINK TO TEST CODE [ http://codepad.org/8CHIepXe ]

C. R. Ward
  • 93
  • 5