YoungProgrammer

Lesson: 5
Problem: 100
Title: The 3n + 1 problem
Difficulty Level: 1
Date: Dec 15, 2008
Site: UVA

This is the first problem of uva site. Given an algorithm which produces a series of integers for a given integer.
The Algorithm is:

for an integer n
n = n/2 if(n is even)
else n = 3*n + 1

For an example, let n = 22

First, n is even, so n = n/2 = 11
Next, n is odd(11), so n = n*3 + 1 = 34
Next again, n is even, so n = n/2 = 34/2 = 17
....
....
Stop when n = 1. It is guaranteed that 1 must be appeared.

for this case, the series is: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1.

Our first job is to count the length of the series for each integer from 1 to 1000000-1 ( read the input specification) and we save it into an array for further calculation.

lets we write a function which takes an integer and return the length of the cicle/series for that number.

int Length(int n) {
int count = 1; // int is enough , read the input specification
if(n == 1) return 1; // i think you get it
while(n > 1) {
count++;
if(n % 2 == 0) n = n / 2;
else
n = n * 3 + 1;
}
return count; // length of the cycle
}

After this, you should call the above function for each integer between 1 and 1000000-1 and save the result into a integer array.

Now come to the most important portion of this problem and it's a trap.

Consider the following input set:
1 10
10 1

Output must be:
1 10 20
10 1 20

Note: The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

Hope you get it.

How to find the maximum cycle length between two given interval ? A simple loop can do this as your results were saved in an array.

See my source code to get an idea to implement. Before, you must try first.