### cycle length of n

```
consider the following algorithm :
if
```*n* = 1 then STOP
if *n* is odd then

else

Given the input 22, the following sequence of numbers will be printed
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is
printed) for any integral
input value.

Given an input

*n*, it is possible to determine the number of numbers printed (including the 1). For a given*n*this is called the*cycle-length*of*n*. In the example above, the cycle length of 22 is 16.
For any two numbers

*i*and*j*you are to determine the maximum cycle length over all numbers between*i*and*j*.

## Sample Input (1<n<1000000)

```
1 10
100 200
201 210
900 1000
```

## Sample Output

```
1 10 20
100 200 125
201 210 89
900 1000 174
```

sir plz tell the approach

ReplyDeleteI can't think of anything except brute-force.

plzz help ??

@above if you will see the pattern you will find that you don't need to recompute values for all n.

ReplyDeleteplease see the code below

#include

#include

using namespace std;

typedef unsigned int uint;

typedef unsigned short ushort;

#define SIZE 1000001

static unsigned short table[SIZE];

ushort print(uint n)

{

if(n < SIZE && table[n])

return table[n];

if(n & 1)

{

if( n < SIZE)

{

table[n] = 2 + print( (3*n+1) >> 1 );

return table[n];

}

else

{

return 2 + print( (3*n+1) >> 1 );

}

}

else

{

if( n < SIZE)

{

table[n] = 1 + print( n >> 1 );

return table[n];

}

else

{

return 1 + print( n >> 1 );

}

}

}

int main()

{

//read and write inputs and outputs to file

freopen("INPUT","r",stdin);

freopen("OUTPUT","w",stdout);

uint x,y,i;

ushort max_count=0,count=0;

table[1] = 1;

while(cin>>x>>y)

{

max_count = 0;

if(x < y)

{

for(i=x;i<=y;i++)

{

count = print(i);

if (count > max_count)

max_count = count;

}

}

else

{

for(i=y;i<=x;i++)

{

count = print(i);

if (count > max_count)

max_count = count;

}

}

cout<<x<<" "<<y<<" "<<max_count<<endl;

}

return 0;

}