UVA 100: The 3n+1 Problem

First Submit: Time Limit Exceeded!

Reason:  I was thinking about building up the whole table from 1 to max(startInt, endInt) in advance. However, this process take too much time, and most of the entries in the table cannot be used during the computation.

Second Submit: Wrong Answer!

Reason:  I forgot to set the result variable back to 0 at the end of each running instance.

Third Submit: Accept!

Source code:

#include <iostream>
using namespace std;

const int size = 1000001;

int table[size] = {0};

int calcCycleLength(int n) {
    if (n < size && table[n])
        return table[n];

    if (n & 1) { // n is odd.
        if (n < size) {
            table[n] = 2 + calcCycleLength( (3 * n + 1) >> 1 );
            return table[n];
        } else {
            return 2 + calcCycleLength( (3 * n + 1) >> 1 );
        }
    } else { // n is even.
        if (n < size) {
            table[n] = 1 + calcCycleLength( n >> 1 );
            return table[n];
        } else {
            return 1 + calcCycleLength( n >> 1 );
        }
    }
}

int main() {
    int startInt, endInt;
    int result = 0, temp;

    table[1] = 1;

    cin >> startInt >> endInt;
    while (!cin.eof()) {

        if (startInt > endInt) {
            int i;

            for (i = endInt; i <= startInt; ++i) {
                temp = calcCycleLength(i);
                if (temp > result)
                    result = temp;
            }

        } else {
            int i;
            for (i = startInt; i <= endInt; ++i) {
                temp = calcCycleLength(i);
                if (temp > result)
                    result = temp;
            }
        }

        cout << startInt << " " << endInt << " " << result << endl;

        result = 0;

        cin >> startInt >> endInt;
    }

    return 0;
}