# 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.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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: