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×106)
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)
}
}