Starting with any positive integer N, we define the Collatz sequence corresponding to N as the numbers formed by the following operations:
If N is even, N→ N/2
if N is odd,   N→ 3N+ 1
It is conjectured but not yet proven that no matter which positive integer we start with; we always end up with 1.
For example, 10 → 5  → 16  → 8  → 4  → 2  → 1. You have to give the maximum collatz sequence length among all the numbers from 1 to N(both included).
Example 1:
Input: N = 1
Output: 1
Explaination: Here N can have only one 
value 1.
Example 2:
Input: N = 3
Output: 8
Explaination: For N= 3 we need to check 
sequence length when sequence starts with 
1, 2, and 3.
when sequence starts with 1, it's : 1 
length = 1
when sequence starts with 2, it's : 2->1, 
length = 2
when sequence starts with 3, it's : 
3->10->5->16->8->4->2->1, length = 8.
Your Task:
You do not need to read input or print anything. Your task is to complete the function collatzLength()which takes N as input parameter and returns the maximum collatz sequence length.
Expected Time Complexity:O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 < N < 10^{6}

Difficulty: EASY
Tags: Dynamic programming

Mathematics
Skill types: Dynamic programming
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



class Solution:

    def collatzLength(self, N):

        # code here

Solutions:
def collatzLenUtil(n, collLenMap):
	if n in collLenMap:
		return collLenMap[n]
	if n == 1:
		collLenMap[n] = 1
	elif n % 2 == 0:
		collLenMap[n] = 1 + collatzLenUtil(n // 2, collLenMap)
	else:
		collLenMap[n] = 1 + collatzLenUtil(3 * n + 1, collLenMap)
	return collLenMap[n]

def collatzLen(n):
	collLenMap = {}
	collatzLenUtil(n, collLenMap)
	(num, l) = (-1, 0)
	for i in range(1, n):
		if i not in collLenMap:
			collatzLenUtil(i, collLenMap)
		cLen = collLenMap[i]
		if l < cLen:
			l = cLen
			num = i
	return (num, l)

class Solution:

	def collatzLength(self, N):
		return collatzLen(N + 1)[1]


class Solution:

	def collatzLength(self, n):
		if n == 0:
			return 0
		if n == 1:
			return 1
		if n == 2:
			return 2
		dp = [-1] * (n + 1)
		dp[1] = 1
		dp[0] = 0
		dp[2] = 2
		maxi = -float('inf')
		for i in range(3, n + 1):
			count = 0
			temp = i
			while temp >= i:
				count += 1
				if temp % 2 == 0:
					temp = temp // 2
				else:
					temp = 3 * temp + 1
			dp[i] = count + dp[temp]
			maxi = max(maxi, dp[i])
		return maxi


class Solution:

	def collatzLength(self, N):
		global maxlength
		found = {}
		maxlength = 0

		def collatzconjecture(N, orig):
			global maxlength
			count = 0
			if N in found:
				return
			while N != 1:
				if N in found:
					found[orig] = found[N] + count
					maxlength = max(maxlength, found[N] + count)
					return
				elif N % 2 == 0:
					N //= 2
					count += 1
				else:
					N = 3 * N + 1
					count += 1
			found[orig] = count + 1
			maxlength = max(maxlength, count + 1)
		for i in range(1, N + 1):
			orig = i
			collatzconjecture(i, orig)
		return maxlength


class Solution:

	def collatzLength(self, N):
		memory = {}

		def step(k):
			if k == 1:
				return 1
			if k in memory.keys():
				return memory[k]
			if k % 2 == 0:
				steps = 1 + step(k // 2)
			else:
				steps = 1 + step(3 * k + 1)
			memory[k] = steps
			return steps
		maxs = 0
		for num in range(1, N + 1):
			steps = step(num)
			if steps > maxs:
				maxs = steps
		return maxs


class Solution:

	def collatzLength(self, N):
		ans = 1
		if N == 0:
			return 0
		if N == 1:
			return 1
		if N == 2:
			return 2
		temp = [0] * N
		temp[0] = 1
		temp[1] = 2
		if N < 3:
			return temp[N]
		for i in range(3, N + 1):
			(j, cnt) = (i, 0)
			while j >= i:
				if j % 2 == 0:
					j //= 2
					cnt += 1
				else:
					j = 3 * j + 1
					cnt += 1
				if j < i:
					cnt += temp[j - 1]
					j = 1
			temp[i - 1] = cnt
			ans = max(ans, temp[i - 1])
		return ans


class Solution:

	def collatzLength(self, N):

		def f(n, memo):
			if n == 1:
				return 1
			if n in memo:
				return memo[n]
			if n % 2 == 0:
				memo[n] = 1 + f(n // 2, memo)
				return memo[n]
			else:
				memo[n] = 1 + f(3 * n + 1, memo)
				return memo[n]
		m = 0
		memo = {}
		for i in range(N, 0, -1):
			m = max(m, f(i, memo))
		return m


import collections

def dictHelper():
	return False

class Solution:

	def Helper(self, n):
		if n == 1:
			return 1
		if self.dp[n] != False:
			return self.dp[n]
		elif n % 2 == 0:
			self.dp[n] = 1 + self.Helper(int(n / 2))
			return self.dp[n]
		else:
			self.dp[n] = 1 + self.Helper(int(3 * n) + 1)
			return self.dp[n]

	def collatzLength(self, N):
		if N < 1:
			return -1
		self.dp = collections.defaultdict(dictHelper)
		max_len = 0
		for i in range(N, 0, -1):
			res = self.Helper(i)
			max_len = max(max_len, res)
		return max_len


class Solution:

	def collatzLength(self, N):
		steps = [0, 1]
		for i in range(2, N + 1):
			count = 0
			while i >= 1:
				if i % 2 == 0:
					i //= 2
					count += 1
					if i < len(steps):
						count += steps[i]
						break
				else:
					i = 3 * i + 1
					count += 1
					if i < len(steps):
						count += steps[i]
						break
			steps.append(count)
		return max(steps)


import sys

class Solution:

	def __init__(self):
		self.cache = {}

	def collatzLength(self, N):
		Kmax = -sys.maxsize - 1
		for i in range(1, N + 1):
			K = self.maxlen(i)
			if K > Kmax:
				Kmax = K
		return Kmax

	def maxlen(self, i):
		if i == 1:
			return 1
		if i == 2:
			return 2
		c = self.cache.get(i, 0)
		if c > 0:
			return c
		if i % 2 == 1:
			c = 1 + self.maxlen(3 * i + 1)
		else:
			c = 1 + self.maxlen(i // 2)
		self.cache[i] = c
		return c


class Solution:

	def cl(self, n):
		if n in self.d:
			return self.d[n]
		if n == 1:
			return 1
		if n % 2 == 0:
			self.d[n] = 1 + self.cl(n // 2)
			return self.d[n]
		else:
			self.d[n] = 1 + self.cl(3 * n + 1)
			return self.d[n]

	def collatzLength(self, N):
		maxi = 0
		self.d = {}
		for i in range(1, N + 1):
			v = self.cl(i)
			maxi = max(maxi, v)
		return maxi