3
\$\begingroup\$

I need the most efficient way to calculate when the Collatz Conjecture of two numbers, a and b respectively, are the same. Here is my algorithm, which is too slow:

while(true) {
        int a = sc.nextInt();
        int b = sc.nextInt();

        if(a == 0 && b == 0) {
            break;
        }

        TreeMap<Integer, Integer> visited = new TreeMap<>();
        visited.put(a, 0);

        int A = a;
        int Acount = 0;

        while(A != 1) {
            Acount++;

            if(A % 2 == 0) {
                A /= 2;
            } else {
                A = A * 3 + 1;
            }

            if(!visited.containsKey(A)) {
                visited.put(A, Acount);
            }
        }

        int B = b;
        int Bcount = 0;

        while(B != 1) {
            if(visited.containsKey(B)) {
                out.println(a + " needs " + visited.get(B) + " steps, " + b + " needs " + Bcount + " steps, they meet at " + B);
                break;
            }

            if(B % 2 == 0) {
                B /= 2;
            } else {
                B = B * 3 + 1;
            }

            Bcount++;
        }

    }

After looking around on Github, I found this, and it worked, although it's essentially the exact same thing.

Original problem

How do I fix my Java code to make it more efficient? I tried it literally at least four times.

\$\endgroup\$
  • \$\begingroup\$ Please do not edit "solutions" into your questions. That would be good form on 90's forums, but here it only results in confusion. Thanks! \$\endgroup\$ – Vogel612 Aug 21 '17 at 9:19
  • \$\begingroup\$ (The alternatives to editing "solutions" into one's question include answering and posting another (cross-linked) question.) \$\endgroup\$ – greybeard Aug 21 '17 at 9:22
  • \$\begingroup\$ I see. Won't do that from now on :) \$\endgroup\$ – Imagine Dragons Aug 22 '17 at 13:27
2
\$\begingroup\$

Integer Overflow

I suspect that your problem has to do with integer overflow and not with your algorithm itself. If you don't guard against integer overflow, doing A = A * 3 + 1 could result in a negative value, and you may end up in an infinite loop where you never reach 1. Try changing your variables to long and resubmit.

By the way, to test for infinite loop cases, try the starting value 113383.

Other suggestions

  • You could use a HashMap instead of a TreeMap. A HashMap has \$O(1)\$ insert and lookup compared to \$O(\log n)\$ for a TreeMap. The difference for this program will be very small though.
  • In the A loop, you shouldn't have to check if visited.containsKey(A) because the collatz sequence never repeats until you reach 1. You can just always add A to the map.
  • If b is 1, your program never prints anything.
\$\endgroup\$
  • \$\begingroup\$ Problem is TLE not WA. I tried a TreeMap still in vain :(. I have to do visited.containsKey(A) because visited maps the first occurrence of A, if I overwrite that value, I lose the index i which associates with number A such that it is at a minimum. It is essential to not overwrite it for the output (per problem statement). \$\endgroup\$ – Imagine Dragons Aug 20 '17 at 6:12
  • \$\begingroup\$ @ImagineDragons If you overflow you can get into an infinite loop, hence TLE. Did you even try it? As far as overwriting the first occurrence, the collatz sequence has no cycles except at 1 so you should never get a second occurrence except at 1. \$\endgroup\$ – JS1 Aug 20 '17 at 6:25
  • \$\begingroup\$ Trying right now, hopefully it works :). How can you prove it has no cycles where 1 < N <= 1 000 000 ? \$\endgroup\$ – Imagine Dragons Aug 20 '17 at 6:31
  • \$\begingroup\$ Hmm now I am getting WA for some reason, but it seems correct... \$\endgroup\$ – Imagine Dragons Aug 20 '17 at 6:38
  • \$\begingroup\$ @ImagineDragons See my latest edit. Your program doesn't work if b is 1. Also, did you remember to change your map to use Long instead of Integer? \$\endgroup\$ – JS1 Aug 20 '17 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.