Skip to content

Instantly share code, notes, and snippets.

Created March 9, 2013 14:06
What would you like to do?
uva 100. 3n+1 Problem
import java.util.*;
class Main {
public static void main(String[] args) throws Exception{
Scanner in = new Scanner(;
PrintWriter out = new PrintWriter(System.out, true);
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;
return n*3+1;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment