CODEWITHSUNDEEP
c++cperformancefibonacci
codeyourstack
codeyourstack

Reputation: 341

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

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

Upvotes: 11

Views: 14944

Answers (6)

Emma
Emma

Reputation: 1

A neat way to solve the problem (I use java). The logic is to utilize the pisano period of 10. To write down the corresponding relationship between Sum(F(n)) = F(n+2) + 1 can help a lot. tip: create a fibonacci sequence alone.

private static long getFibonacciSum(long n) {
    n = (n + 2) % 60;
    long[] fib = new long[(int) n + 1];
    long cor;
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++) {
        fib[i] = (fib[i - 1] + fib[i - 2]) % 10;
    }
    if (fib[(int) n] == 0) cor = 9;
    else cor = fib[(int) n] - 1;
    return cor;
}

Upvotes: 0

Partho KR
Partho KR

Reputation: 132

Last digit of Fibonacci sum repeats after 60 elements.

Here the period is 60 [0-59]. So to get the last digit of n'th sum of number is the last digit of n%60'th sum of number

#include <iostream>
#include <vector>
#include <algorithm>
int get_last_digit(int n){
  std::vector<int> last_digits(60);
  long long a = 0, b = 1;
  last_digits[0] = 0;
  last_digits[1] = 1;
  long long temp, sum = 1;
  // Fill last_digits vector with the first 60 sums last digits
  for (int i = 2; i < 60; i++) {
    temp = a+b;
    a = b;
    b = temp;
    sum += temp;
    last_digits[i] = sum%10;
  }
  // Now return n%60'th element
  return last_digits[n%60];
}
int main(int argc, char const *argv[]) {
  int n;
  std::cin>>n;
  std::cout << get_last_digit(n);
  return 0;
}

Upvotes: 1

Yegor Shapanov
Yegor Shapanov

Reputation: 61

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

}

Upvotes: 6

codeyourstack
codeyourstack

Reputation: 341

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

Upvotes: 18

marshal craft
marshal craft

Reputation: 447

For your function removing the array. 

#include "stdafx.h"
#include <iostream>
using namespace std;
int calc_fib(long long int n) {

    int fibzero = 0;
    int fibone = 1;
    int fibnext;
    long long int res = 1;
    for (long long int i = 2; i <= n; i++) {

        fibnext = (fibone + fibzero) % 10;
        fibzero = fibone;
        fibone = fibnext;
        res = res + fibnext;
    }
    return (res % 10);
}

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

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

Upvotes: 1

shole
shole

Reputation: 4094

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.

Upvotes: 4

Related Questions