Thursday, September 27, 2007

3n + 1 problem

Phewwww...At last i got my first correct submission at UVa online judge. Not anything spectacular. Its the same old 3n + 1 problem....Here is the perfect working code
____________________________________________________________________
Question: 3n + 1 problem
____________________________________________________________________
#include "iostream.h"

int cyclen[1000001];

int findCycleLength(int num) {
int l = 0, index = num;
long long n = num;
if(cyclen[n] != 0) return cyclen[n];
while(n != 1) {
if(n <= 1000000) if(cyclen[n] != 0 ) return cyclen[index] = l + cyclen[n];
if(n % 2 == 0) n/= 2;
else n = 3 * n + 1;
l++;
}
return cyclen[index] = l + 1;
}

int main()
{
int i,j;

while(true) {
cin >> i >> j;
if(cin.eof()) break;
int min = (i < j)? i : j;
int max = (i > j)? i : j;
int maxlen = 0,len;
for(int k = 0; k <= 1000000; k++) cyclen[k] = 0;
for(int k = min; k <= max; k++) if((len = findCycleLength(k)) > maxlen) maxlen = len;
cout << i << " " << j << " " << maxlen << endl;
}
return 0;
}

____________________________________________________________________

No comments:

Contributors