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

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

## 7 thoughts on “UVa 100. The 3n+1 Problem: Solving with a Brute-force Algorithm”

1. enamul says:

which language is perfect for coding

2. Satyam says:

What is the advantage of using PrintWriter ?

1. Md.AdilAkhter says:

Hi Satyam,

Thanks for your question. My rationale is as follows.

In this context, I have used it just to reduce the code size (being a lazy coder, I don’t like writing `System.out.println`;) ). Plus, using a `PrintWriter`, you could output in some other format (if you wish) instead of only in `console`, which effectively restricts the dependency to just one place (good from design perspective too;). see Dependency Inversion Principle).

Please visit http://stackoverflow.com/questions/9494327/writing-to-console-with-system-out-and-printwriter to know more about the differences. I hope it helps!

1. Satyam says: