• Post Reply Bookmark Topic Watch Topic
  • New Topic

Finding the 'ArrayList' with the greatest length  RSS feed

 
Harry Orson
Greenhorn
Posts: 12
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am solving a task linked to the Collatz Problem. I have created a method that produces 1 from any starting number:

The next part of my task is finding a method which will find the longest Collatz sequence below 1,000,000.

I came up with several solutions such as the one below..of course none of them worked.

Could anyone please help and guide me to finding the correct methods for finding the longest Collatz sequence using the comparison of 2 or more ArrayLists. If there are better options than the use of an ArrayList I more than welcome these methods.
Thanks.
 
Campbell Ritchie
Marshal
Posts: 56576
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
There are all sorts of approaches to Collatz, with or without Lists. It shou‍ld be easy enough to compare the number of elements in Lists or other Collections; have a look at some of their methods. Hint: it isn't called length. Try size.

Why are you calling the List calc? Why have you got it as a local variable? You cannot compare Lists if they are separated by being out of scope to each other. Why have you got the if‑else in line 14? Why are you testing for value == 1 inside the loop in line 21?
 
Campbell Ritchie
Marshal
Posts: 56576
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You appear to have found the size() method. I think the problem is that you have got that List as a local variable. If you get it out of that method into another method, you can compare different sizes of Lists.
 
Campbell Ritchie
Marshal
Posts: 56576
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can you create a sort of Sieve of Eratosthenes like algorithm for filling in Collatz paths? Can you create a Map<Integer, List<Integer>> to contain Collatz paths? Let's look at a Collatz path:-
Coll₅₀ = 25→76→38→19→58→29→88→44→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1 which is 24 moves.
You would want a recursive approach, with the base case being Coll₁ = []. Now, the only way you can get to Coll₁ is from Coll₂ which means Coll₂ = 2→Coll₁. That won't work for Coll₃, but you can calculate Coll₄ from that. You can keep doubling, and every time you encounter an even number which matches 3i + 1 (i % 3 == 1), you can both double it and subtract a and divide by 3. You have now reached a branching point.
When you have filled the entire tree, you have 1000000 paths.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!