Counting terms in Collatz sequences until 1 is reached or a limit is exceeded My friend and I are into competitive programming and we wrote two very similar programs for a problem. His got accepted with a runtime of 0.6 s while mine didn't get accepted even after 3 s.

I was hoping somebody could explain to me as to why the addition of one function slowed down my code so much.

Both programs produce the correct output. No issues on that front.

The Question: Given A, the initial value of a Collatz sequence, and some limit L, count the number of terms until either 1 is reached or L is exceeded.  A and L are both smaller than 231.

His Code


#include&lt;iostream&gt;

using namespace std;

int main(){
    long long A,L;
    int cont,caso=1;

    while(1){
        cin&gt;&gt;A&gt;&gt;L;
        if(A&lt;0 &amp;&amp; L&lt;0) break;

        cout&lt;&lt;"Case "&lt;&lt;caso&lt;&lt;": A = "&lt;&lt;A&lt;&lt;", limit = "&lt;&lt;L&lt;&lt;", number of terms = ";
        caso++;

        cont=0;

        while(A&lt;=L &amp;&amp; A!=1){
            if(A%2==0) A/=2;
            else A=3*A+1;

            cont++;
        }

        if(A==1) cont++;

        cout&lt;&lt;cont&lt;&lt;endl;
    }

    return 0;
}



My Code

#include&lt;iostream&gt;

using namespace std;

bool even(int a)
{
    if(a%2==0)
        return true;
    else
        return false;
}

int main()
{
    int n=0;
    while(1)
    {
        long long int a, limit;
        cin&gt;&gt;a&gt;&gt;limit;
        if((a==-1) &amp;&amp; (limit==-1))
            break;
        cout&lt;&lt;"Case "&lt;&lt;n&lt;&lt;": A = "&lt;&lt;a&lt;&lt;", limit = "&lt;&lt;limit&lt;&lt;", number of terms = ";
        int val=a;
        int count=0;
        while((val&lt;=limit) &amp;&amp; (val!=1))
        {
            if(even(val))
                val/=2;
            else
                val=(val*3) + 1;
            count++;
        }
        if(a==1)
            count++;
        cout&lt;&lt;count&lt;&lt;endl;
    }
    return 0;
}
Overflow Bug

The reason your program is timing out is because your variable val is defined as an int instead of a long long.  Because of this, val can become negative during the line val=(val*3) + 1, which leads to an infinite loop.  You should change the type of val to long long.  If you want to test the infinite loop yourself, try this test case and see what happens:

113383 2147483647


Output Bug

Your program has two output related errors:


You should initialize n=1 instead of n=0.
Your code is missing the line n++.


The above two problems mean that your program is outputting something like:

Case 0: A = 100, limit = 100000, number of terms = 25
Case 0: A = 101, limit = 100000, number of terms = 25


instead of the correct format of:

Case 1: A = 100, limit = 100000, number of terms = 25
Case 2: A = 101, limit = 100000, number of terms = 25