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

you forgot the return type - also `unsigned` is `unsigned int` and not `unsigned long long` — BeyelerStudios, Jul 05 '20 at 17:59
These aren't regular Fibonacci numbers, so could you briefly explain the maths involved. It's hard to work out where you're going wrong when I don't know what the code is supposed to do. — john, Jul 05 '20 at 17:59
Does this answer your question? [int to unsigned int conversion](https://stackoverflow.com/questions/4975340/int-to-unsigned-int-conversion) — BeyelerStudios, Jul 05 '20 at 18:04

score 1 · Accepted Answer · answered Jul 05 '20 at 18:02

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.

answered Jul 05 '20 at 18:02

Telescope

2,068
1
5
22

1

While I'm sure you are right about the problem in this case the figures you are quoting are completely platform dependent. C++ only specifies minimum ranges that the various integer types must support. – john Jul 05 '20 at 18:06
Ok will look into BigNums and see if I can solve it then – BlueFits Jul 05 '20 at 18:11
Yea this works, however, using it in hacker rank is no go because I cant use other libraries on that website. I guess it just isn't doable in hacker rank or at least isn't practical – BlueFits Jul 05 '20 at 18:38
Why not? The implementation for a BigNum isn't extremely complicated. – Telescope Jul 05 '20 at 18:43

Modified Fibbonaci C++ getting a large negative number

1 Answers1