UVa 100: The 3n + 1 problem

UVa 100: The 3n + 1 problem

Written by on 18 April 2012

Topics: UVa Online Judge

The problem (or UVa 100) is the first problem at UVa’s online judge. The problems there are not in any particular order, as can be seen from this first problem which is far from being the easiest (but also very far from being the hardest). You can read the problem statement here or here.

Interpretation

This problem is very similar to Project Euler 14. We are dealing with Collatz sequences (also known as Hailstone numbers), and are asked to find the length of the longest Collatz sequence starting at any number between and (inclusive), where and are numbers that are given to us as input.

We must be very careful when reading the problem statement. We need to gather as much knowledge as possible about the input and be careful not to assume anything that is not specifically stated. Here we are given that and are both integers between and (exclusive). Now many people could wrongly assume that is less than (because that would be the most natural way for them to be given to us), but it’s never said that would be less than , and therefore we cannot assume that. A solution that would assume that would get a Wrong Answer verdict from the online judge.

Brute Force

Just like we did in Project Euler 14, we are going to create a brute-force solution to solve the problem. But first of all, since we’re dealing with Collatz sequences, we should create a helper function to calculate the number that comes after a given number in the sequence. It’s pretty trivial and should look something like:

// a function that returns the
// next number in the sequence
public static long next(long n) {
	if (n % 2 == 0)
		return n / 2;       // if n is even
	else
		return 3 * n + 1;   // if n is odd
}

Next we need to calculate a given numbers cycle length. We can either do it iteratively (which is probably faster) or we can do it recursively (which might cause stack overflow, but ends up being more beautiful code). I’m going to go with the recursive implementation because of what we are going to do in the next section. will be our base case with a length of , and our recursive case will be that the cycle length of the current number is one greater than the cycle length of the next number.

public static int cycleLength(long n) {
	// our base case
	// 1 has a cycle length of 1
	if (n == 1)
		return 1;

	// the cycle length of the current number is 1 greater
	// than the cycle length of the next number
	int length = 1 + cycleLength(next(n));

	return length;
}

The last thing we have to do to get a working solution is to implement the main method. We need a while-loop that reads the test cases and then we need to loop through all the numbers from to and find the minimum cycle length. Then we must output the result in exactly the same format as the problem statement tells us to (even the smallest extra whitespace could cause an otherwise working solution to fail), which in this case tells us to output , and the minimum cycle length on one line, with one space between them, in this order. Remember that doesn’t have to be smaller than , so we have to take special care when looping through the numbers (that is, we have to loop from to if we’re using a conventional for-loop).

public static void main(String[] args) throws Exception {
	Scanner in = new Scanner(System.in);
	PrintWriter out = new PrintWriter(System.out, true);

	// while there is some input to read
	while (in.hasNextInt()) {
		int i = in.nextInt(),
		    j = in.nextInt(),
		    from = Math.min(i, j),
		    to = Math.max(i, j),
		    max = 0;

		// loop through all the numbers
		// and find the biggest cycle
		for (int n = from; n <= to; n++) {
			max = Math.max(max, cycleLength(n));
		}

		out.printf("%d %d %d\n", i, j, max);
	}
}

Now our solution is complete. Well, almost. Our solution might be too slow, since it has to solve all allowed inputs in under 3 seconds. We’re not sure, but we don’t want to take any unnecessary risk, so we might as well optimize it a bit. Which brings us to the next section.

Caching

We calculate the cycle length for some of the numbers again and again and again. Therefore it’s a good idea to save (aka. cache) what we’ve computed, so we don’t have to compute it again. Here we are going to have an array for our cache, where the -th element is the cycle length of the number . Note that a cycle length of  for the -th element means that we haven’t calculated it yet. I’ve decided to only cache the results for smaller than , since that is the range we are mostly dealing with in this problem (take a look at the post and comments of Project Euler 14 for some discussion about this).

We only need to make small changes to our cycleLength function to cache the results, since we went with the recursive approach.

// cache for already computed cycle lengths
public static int[] cache = new int[1000000];

public static int cycleLength(long n) {
	// our base case
	// 1 has a cycle length of 1
	if (n == 1)
		return 1;

	// check if we've already cached the
	// cycle length of the current number
	if (n < 1000000 && cache[(int)n] != 0)
		return cache[(int)n];

	// the cycle length of the current number is 1 greater
	// than the cycle length of the next number
	int length = 1 + cycleLength(next(n));

	// we cache the result if the
	// current number is not too big
	if (n < 1000000)
		cache[(int)n] = length;

	return length;
}

Conclusion

We started off by writing a straightforward recursive solution to our problem. We then optimized it by caching cycle lengths that we had already computed and now our solution is fast enough to get Accepted at the online judge.

You can take a look at the complete source code here.
So what do you think? Did/would you solve it differently? Let me know in the comments.

5 Comments For This Post I'd Love to Hear Yours!

  1. mathlover says:

    This will not work for the range of numbers upto 1,000,000.
    For example if you try 15, it ends up making a recursive call to 160.
    15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
    160 is much greater than 15.
    If you try running it on 1,000,000 it will make a call to a number much bigger, which your algorithm does not support.

  2. Bjarki Ágúst says:

    You must be misunderstanding something, because the code does indeed work for numbers bigger than 1,000,000.

    The thing is that I only cache (save the results) for numbers less than 1,000,000. Numbers bigger than that still get computed, but the results are not saved for later use.

  3. Is there any way to make the cycleLength method iteratively (way faster) and keep using the caching strategy? I’m trying to do that without success.

  4. Bjarki Ágúst says:

    Yes, that is absolutely possible. We could change the cycleLength function as follows.

    public static int cycleLengthIterative(long n) {
    
        int length = 0;
        Queue<Long> chain = new LinkedList<Long>();
    
        while (true) {
            if (n == 1) {
                length += 1;
                break;
            } else if (n < 1000000 && cache[(int)n] != 0) {
                length += cache[(int)n];
                break;
            }
    
            length += 1;
            chain.add(n);
            n = next(n);
        }
    
        int tempLen = length;
    
        while (!chain.isEmpty()) {
            n = chain.remove();
    
            if (n < 1000000)
                cache[(int)n] = tempLen;
    
            tempLen--;
        }
    
        return length;
    }
    

    The code remembers the first part of the chain until it hits a value that has already been computed. It then walks through this part of then chain an updates the cache accordingly.

    But I should add that this method is slower according to UVa. The recursive solution has a running time of 0.312s while the iterative solution has a running time of 0.439s.

  5. ssavi says:

    What does it says in those input and output of this problem ??

    How 1 10 gets the output 20 ?? Can you please give me the derivation ??

Leave a Comment Here's Your Chance to Be Heard!

You can use these html tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

You can use short tags like: [code language="language"][/code]

The code tag supports the following languages: as3, bash, coldfusion, c, cpp, csharp, css, delphi, diff,erlang, groovy, javascript, java, javafx, perl, php, plain, powershell, python, ruby, scala, sql, tex, vb, xml

You can use [latex]your formula[/latex] if you want to format something using latex

Notify me of comments via e-mail. You can also subscribe without commenting.