fibanocci.cpp

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

deque<int> addDeques(deque<int>& num1, deque<int>& num2);

int main()
{
    deque<int> number1;
    deque<int> number2;
    deque<int> out;

    int n = 0;
    int parentSize = 0;
    int outSize = 0;

    //first 2 values of Fibonacci series..
    number1.push_back(0);
    number2.push_back(1);


    //cout << "Enter Fibonacci (n): " <<endl;
    cin >> n;


    vector<deque<int>> parent;
    parentSize = n+1;
    parent.push_back(number1);
    if(parentSize > 1){
    parent.push_back(number2);
    }


        for(int i=2; i < parentSize; i++){
            out = addDeques(parent[i-1], parent[i-2]);
            parent.push_back(out);
        }

    deque<int> output = parent.back();
    outSize = output.size();
    //cout << "Output Size: " << outSize << " digits." <<endl<<endl;
    //cout << "RESULT: "<< endl;
    int last_digit = 0;

    last_digit = output.back();
    //De-Parse the solution
    //for(int j=0; j < outSize; j++){

        //cout <<output.at(j);
    //last_digit = output.at(j);
   // }
    cout << last_digit;
    cout << endl;
    return 0;
}

deque<int> addDeques(deque<int>& num1, deque<int>& num2){
    int d_size = 0;
    int num1_size = num1.size();
    int num2_size = num2.size();
    int remainder = 0;
    deque<int> result;


    if(num1_size > num2_size){
        d_size = num1_size;
        //adjust the size of both numbers by adding zeros at the beginning
        for(int j=0; j < (num1_size - num2_size); j++){
            num2.push_front(0);
        }
    }else if(num1_size == num2_size){
        d_size = num1_size;

    }else{
        d_size = num2_size;
        //adjust the size of both numbers by adding zeros at the beginning
        for(int k=0; k < (num2_size - num1_size); k++){
            num1.push_front(0);
        }
    }

    for(int i=d_size; i > 0; i--){
        //Get the mirrored index
        int index = i-1;
        int first_num = num1.at(index);
        int second_num = num2.at(index);
        int temp_sum = 0;


        //Split 2 digits number ..
        if((first_num + second_num + remainder) > 9){
            temp_sum = (first_num + second_num + remainder) % 10;
            result.push_front(temp_sum);

            remainder = (first_num + second_num + remainder) / 10;
        }else{
            result.push_front(first_num + second_num + remainder);
            remainder = 0;
        }
    }
    //in case of overflow..
    if(remainder > 0){
        result.push_front(remainder);
    }
    return result;
}