3n+1 solution giving wrong answer

Question

This is my solution to 3n+1 problem which is giving wrong answer. I have struggled on this one quiet a lot many times since the last 5 days. Please help me figure out the problem in my solution. I have used tail recursion and am also storing a map to track the powers of 2 to reach to the answer quicker. The link to the problem is Programming Challenges - The 3n + 1 problem

#include <stdio.h>
#include <map>
using namespace std;

#define MAX 1000000
typedef long long int ll;
map<int, int> globalMap;

void process(){
  ll i = 1, key = 1, value = 1;
  while(value < MAX){
    globalMap[value] = key;
    key++; value *= 2;
  }
  return;
}

ll cycleLength(ll n, ll ans){
  if(n == 1) return ans; 
  if(globalMap.find(n) != globalMap.end()) return ans+globalMap[n];
  else{
    if(n%2){
      return cycleLength(3*n+1, ++ans);
    }
    else return cycleLength(n/2, ++ans);
  }
}
int main(){
  ll i, j, temp, max=-1;
  process();
  while(scanf("%lld%lld", &i, &j) != EOF){
    max = -1;
    for(ll a = i; a <= j; ++a){
      temp = cycleLength(a, 0);
      if(max < temp) max = temp;
    }
    printf("%lld %lld %lld\n", i, j, max);
  }
  return 0;
}

Answer 1

Your process() function will populate globalmap such that the cycle length of 1 is 1, but your cyclelength function returns a cycle length of 0 if passed in ll = 1 and ans = 0.

So, on the following input:

1 1

1 2

Your program will output:

1 1 0
1 2 2

This seems like it might be the sticking point with your sol'n.

Answer 2

Your solution will not work if i>j.

Try iterating from the minimum of i,j to the maximum of i,j instead.

Note that i and j have to be printed in the original order, so don't just swap i and j if they are in the wrong order.