c++ - Modified Fibbonaci C++ getting a large negative number

Question

Ok so, I'm doing hackerrank's Fibonacci modified question. I am able to solve this question only when the iteration goes to 8 anything pass that and it starts returning a large negative number. I thought this was because of an integer overflow so I changed my types to unsigned long long yet the problems still persist. Any help is appreciated.

Link to original problem: https://www.hackerrank.com/challenges/fibonacci-modified/problem

    #include <iostream>
    #include <vector>
    
    using namespace std;
    
    int modFib(unsigned t1, unsigned t2, unsigned n) {
        if (n == 1) {
            return t1;
        } 
        else if (n == 2) {
            return t2;
        } else {
            return modFib(t1, t2, n-2) + (modFib(t1, t2, n-1) * modFib(t1, t2, n-1));
        }
    }
    
    int main() {
        cout << modFib(0, 1, 10) << endl;
        return 0;
    }

//Expected output is 84266613096281243382112
//I get -1022889632

标签： c++fibonacci

Answer 1

In C++, the general range of an unsigned int is 0 to 4,294,967,295, so using an unsigned int will not be appropriate for this problem.

The expected output is actually larger than the maximum possible value of even an unsigned long long int, which goes from 0 to 18,446,744,073,709,551,615. This means that you cannot use either of these data types for this problem.

For such large values, you should look into the usage of BigNums.