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

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

See Also

see Collatz Problem a.k.a. 3n+1 ProblemCollatz Problem a.k.a. 3n+1 Problem.
see UVa 371. Ackermann FunctionUVa 371. Ackermann Function.

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

  1. Pingback: UVa 371. Ackermann Function | Adil Akhter's
  2. Pingback: Collatz Problem a.k.a. 3n+1 Problem | Adil Akhter's

    1. 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!

      Regards, Adil

      Reply

Leave a comment