UVa : 100 (The 3n + 1 Problem)

Pitfalls:

1. i can be greater than j
2. If you use an array, recall that large odd values (e.g. 999999) will map to 3*n + 1

Verdict: Accepted
Runtime: 0.956

// START CODE
#include <iostream>
#include <stdio.h>
#include <stack>
#include <map>
#include <algorithm>

#define MAX 1000000

using namespace std;

map<int, int> m;

int next(int n) {
  if (n % 2 == 1)
    return 3 * n + 1;
  else
    return n / 2;
}

int cycleLength(int n) {
  int save = n;
  stack<int> s;
  while (m.find(n) == m.end()) {
    s.push(n);
    n = next(n);
  }
  while (!s.empty()) {
    m[s.top()] = 1 + m[n];
    n = s.top();
    s.pop();
  }
  return m[save];
}

int main() {
  m[1] = 1;

  while (1) {
    int i, j;
    cin >> i >> j;
    if (cin.eof())
      break;
    printf("%d %d ", i, j);
    if (i > j)
      swap(i, j);
    int m = 1;
    for (; i <= j; i++)
      m = max(m, cycleLength(i));
    printf("%d\n", m);
  }
}
// END CODE