The Collatz Sequence problem

Posted by Gandalf StormCrow on Stack Overflow See other posts from Stack Overflow or by Gandalf StormCrow
Published on 2010-04-05T13:23:11Z Indexed on 2010/04/05 13:33 UTC
Read the original article Hit count: 595

Filed under:
|

I'm trying to solve this problem, its not a homework question, its just code I'm submitting to uva.onlinejudge.org so I can learn better java trough examples. Here is the problem sample input :

 3 100
 34 100
 75 250
 27 2147483647
 101 304
 101 303
 -1 -1

Here is simple output :

 Case 1: A = 3, limit = 100, number of terms = 8
 Case 2: A = 34, limit = 100, number of terms = 14
 Case 3: A = 75, limit = 250, number of terms = 3
 Case 4: A = 27, limit = 2147483647, number of terms = 112
 Case 5: A = 101, limit = 304, number of terms = 26
 Case 6: A = 101, limit = 303, number of terms = 1

The thing is this has to execute within 3sec time interval otherwise your question won't be accepted as solution, here is with what I've come up so far, its working as it should just the execution time is not within 3 seconds, here is code :

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    Scanner stdin = new Scanner(System.in);
    int start;
    int limit;
    int terms;
    int a = 0;

    while (stdin.hasNext()) {
      start = stdin.nextInt();
      limit = stdin.nextInt();
      if (start > 0) {
        terms = getLength(start, limit);
        a++;
      } else {
        break;
      }
      System.out.println("Case "+a+": A = "+start+", limit = "+limit+", number of terms = "+terms);
    }
  }

  public static int getLength(int x, int y) {
    int length = 1;
    while (x != 1) {
      if (x <= y) {
        if ( x % 2 == 0) {
          x = x / 2;
          length++;
        }else{
          x = x * 3 + 1;
          length++;
        }
      } else {
        length--;
        break;
      }
    }

    return length;
  }
}

And yes here is how its meant to be solved :

An algorithm given by Lothar Collatz produces sequences of integers, and is described as follows:

Step 1:
    Choose an arbitrary positive integer A as the first item in the sequence. 
Step 2:
    If A = 1 then stop. 
Step 3:
    If A is even, then replace A by A / 2 and go to step 2. 
Step 4:
    If A is odd, then replace A by 3 * A + 1 and go to step 2. 

And yes my question is how can I make it work inside 3 seconds time interval?

© Stack Overflow or respective owner

Related posts about java

Related posts about algorithm