Longest Collatz sequence in Scala

Question

I am trying to find the longest Collatz Sequence:

Which starting number, ≤ N, produces the longest chain? If many possible such numbers are there print the maximum one. (1 ≤ N ≤ ×ばつ10⁶)

I tried optimizing the code to include memoization still getting Time Limit Exceeded, for these solutions. Wanted some help to understand where the method is consuming time.

Implementation Using HashMap As Memoized Cache:

object CollatzSeq {
 private final val mapOfCollatzSequence = 
 scala.collection.mutable.HashMap[BigInt, BigInt]()
 .withDefaultValue(0)
 def longestCollatzSeq(n: BigInt): BigInt = {
 def longestCollatzSeqHelper(n: BigInt, count: BigInt = 0): BigInt = {
 val mapValueOfN = mapOfCollatzSequence(n)
 n match {
 case n if n == 1 => count
 case _ if mapValueOfN != 0 =>
 count + mapValueOfN
 case n if n % 2 == 0 =>
 val updateForEven = longestCollatzSeqHelper(n/2, count + 1)
 mapOfCollatzSequence.update(n, updateForEven - count)
 updateForEven
 case n if n % 2 != 0 =>
 val c = longestCollatzSeqHelper(3 * n + 1 , count + 1)
 mapOfCollatzSequence.update(n, c - count)
 c
 }
 }
 longestCollatzSeqHelper(n)
 }
}

Implementation Using Array As Memoized Cache:

object CollatzSeq {
 // Using Array As Performance Is Better Than Map
 private final val collatzSeq = Array.fill[BigInt](5* 1000 * 1000)(0)
 def longestCollatzSeq(n: BigInt): BigInt = {
 def longestCollatzSeqHelper(n: BigInt, count: BigInt = 0): BigInt = {
 val countOfN = collatzSeq((n - 1).toInt)
 n match {
 case n if n == 1 => count
 case _ if countOfN != 0 =>
 count + countOfN
 case n if n % 2 == 0 =>
 val updateForEven = longestCollatzSeqHelper(n/2, count + 1)
 collatzSeq.update((n-1).toInt, updateForEven - count)
 updateForEven
 case n if n % 2 != 0 =>
 val updateForOdd = longestCollatzSeqHelper(3 * n + 1 , count + 1)
 collatzSeq.update((n-1).toInt, updateForOdd - count)
 updateForOdd
 }
 }
 longestCollatzSeqHelper(n)
 }
}

Performance Reference

• Graipher: Hey welcome to Code Review! Please add some description about what problem your code solves (i.e. a quote from the the problem description). This is because links can rot and a question should be as self-contained as possible.
• Shankar Shastri: @Graipher, Updated the question.

Answer 1

There are a few things you could do to make what you've got a bit faster:

1. The numbers get quite big but BigInt is overkill (and slow). The longestCollatzSeqHelper() method will have to deal with values in the Long domain, but the problem set, and results, are well within the Int range, which will be faster.
2. Because of the large numbers, you're cache could grow immensely. Perhaps beyond system resources.
3. You're testing n as many as 4 times per iteration. That can be reduced to 2.

But this is mere window dressing. When you encounter HackerRank timeout limits, code optimization usually doesn't get you very far. 9 times out of 10 you need to go back, re-examine the problem statement, and rethink your approach to it.

When I tackled this problem I started by caching calculations, but eventually I gave that up and started focusing on the other end:

1. To find the longest Collatz length for numbers <= N, I don't have to count the Collatz length for every number below N. There's a threshold below which it is impossible for the C-length to surpass the lengths for numbers above that threshold.
2. Some numbers don't need to have their Collatz length calculated at all. Due to a simple mathematical property it is impossible for its C-length to surpass its neighbors.

With this in mind, and caching for reuse only individual results within a problem set, you should be able to pass this challenge.