Tribonacci number program doesnt return false

June 11, 2022

For each number read from the standard input the program should print YES if it is a Tribonacci number and NO otherwise. What am I doing wrong in my program, it prints YES, but it wont print NO when the number is not a tribonacci number. For example when number is 45, it should print no.

Tribonacci number formula

T0=0
T1=1
T2=2
Tn=Tn-1 + Tn-2 + Tn-3 (for n>2)

using namespace std;

bool isTrib(int n) {
    if(n==0 || n == 1 || n == 2) {
        return true;
    }
    if(n > 2) {
        int trib = isTrib(n-1)+isTrib(n-2)+isTrib(n-3);
        if(trib == n) {
            return true;
        }
    }
   return false; 
}
   

int main()
{
    int n;
    while(cin>>n) {
        bool result = isTrib(n);
        cout << result;
        result == 1 ? cout << "YES" << endl : cout << "NO" << endl;
    }
    return 0;
}

>Solution :

you’re mixing two things: actual tribonacci numbers and "true"/"false" answer to question "whether N is tribonacci", for example variable trib in your code can be either 0, 1, 2 or 3, it cannot take any other values, but you’re trying to compare it with real number, which is apples to oranges

here is fixed version:

bool isTrib(int n) {
    if(n==0 || n == 1 || n == 2) {
        return true;
    }
    
    int n1 = 0;
    int n2 = 1;
    int n3 = 2;
    
    int trib = n1 + n2 + n3;
    while (trib <= n) {
        if (trib == n) return true;
        
        n1 = n2;
        n2 = n3;
        n3 = trib;
        trib = n1 + n2 + n3;
    }
    return false;
}
   

int main()
{
    int n;
    while(cin>>n) {
        bool result = isTrib(n);
        cout << (result ? "YES" : "NO") << endl;
    }
    return 0;
}