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 ≤ 5×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

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.