The UVa 100: The 3n+1 Problem is about collatz problem, which we have discussed in details in a recent post. The following Java code describes a brute-force algorithm to solve this problem. In addition, a memoization technique is incorporated to reduce redundant computations and thereby, to enhance efficiency of this brute-force algorithm.

	import java.util.*;
	import java.io.*;

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

	while(in.hasNextInt()){
	int i = in.nextInt();
	int j = in.nextInt();

	int from = Math.min(i, j);
	int to = Math.max(i, j);

	int max = 0;

	for (int ii = from;ii<=to;ii++){
	max = Math.max(max, computeCycleLength(ii));
	}

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

	}

	private static int computeCycleLength(long n) {

	if (n==1)
	return 1;
	if (n<_MaxValue && memo[(int)n] != 0)
	return memo[(int)n];

	// computing length of collatz cycle
	int len = 1 + computeCycleLength(nextCollatz(n));

	// storing it in cache
	if (n<_MaxValue)
	memo[(int)n] = len;
	return len;
	}


	private static int _MaxValue = 1000000;
	public static int[] memo = new int[_MaxValue];

	public static long nextCollatz(long n){

	if (n%2==0)
	return n/2;
	else
	return n*3+1;
	}
	}

view raw uva100.java hosted with ❤ by GitHub

Please leave a comment if you have any query. Thank you.

Tag: uva

UVa 100. The 3n+1 Problem: Solving with a Brute-force Algorithm

See Also