Given a number N. Find the minimum number of operations required to reach N starting from 0. You have 2 operations available:
	Double the number 
	Add one to the number
Example 1:
Input:
N = 8
Output: 4
Explanation: 0 + 1 = 1, 1 + 1 = 2,
2 * 2 = 4, 4 * 2 = 8
Ã¢â¬â¹Example 2:
Input: 
N = 7
Output: 5
Explanation: 0 + 1 = 1, 1 + 1 = 2,
1 + 2 = 3, 3 * 2 = 6, 6 + 1 = 7
Your Task:
You don't need to read input or print anything. Your task is to complete the function minOperation() which accepts an integer N and return number of minimum operations required to reach N from 0.
Expected Time Complexity: O(LogN)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Greedy algorithms

Starter code: #User function Template for python3

class Solution:
    def minOperation(self, n):
        # code here 

Solutions:
class Solution:

	def minOperation(self, n):
		dp = [n + 1 for i in range(n + 1)]
		dp[0] = 0
		for i in range(1, n + 1):
			if i % 2 == 0:
				dp[i] = min(dp[i], dp[int(i // 2)] + 1)
			else:
				dp[i] = min(dp[i], 1 + dp[i - 1])
		return dp[-1]


class Solution:

	def minOperation(self, n):
		steps = 0
		while n > 0:
			if n % 2 == 0:
				n = n // 2
			else:
				n = n - 1
			steps += 1
		return steps


class Solution:

	def minOperation(self, n):
		count = 0
		while n > 0:
			if n == 1 or n % 2 == 0:
				count += 1
			else:
				count += 2
			n //= 2
		return count


class Solution:

	def minOperation(self, n):
		x = [0 for i in range(n + 1)]
		x[n - 1] = 1
		for i in range(n - 2, -1, -1):
			if 2 * i > n or i == 0:
				x[i] += 1 + x[i + 1]
			else:
				x[i] += 1 + min(x[2 * i], x[i + 1])
		return x[0]


class Solution:

	def minOperation(self, n):
		T = list(range(10 ** 6 + 1))
		for i in range(2, n + 1):
			T[i] = min(T[i - 1], T[i // 2] + (i % 2 == 1)) + 1
		return T[n]


class Solution:

	def recur(self, ind, dp):
		if ind == 0:
			return 0
		if dp[ind] != -1:
			return dp[ind]
		one = float('inf')
		if ind % 2 == 0:
			one = 1 + self.recur(ind // 2, dp)
		two = 1 + self.recur(ind - 1, dp)
		dp[ind] = min(one, two)
		return dp[ind]

	def minOperation(self, n):
		dp = [0] * (n + 1)
		dp[0] = 0
		dp[1] = 1
		for i in range(2, n + 1):
			one = float('inf')
			if i % 2 == 0:
				one = 1 + dp[i // 2]
			two = 1 + dp[i - 1]
			dp[i] = min(one, two)
		return dp[n]


class Solution:

	def minOperation(self, n):
		remainder = 0
		c = 1
		while n != 1:
			r = n % 2
			n = n // 2
			remainder += r
			c += 1
		return c + remainder


from functools import lru_cache

class Solution:

	def minOperation(self, n):
		dp = [0] * (n + 1)
		dp[1] = 1
		for i in range(2, n + 1):
			if i % 2 != 0:
				dp[i] = 1 + dp[i - 1]
			else:
				dp[i] = min(1 + dp[i - 1], 1 + dp[int(i / 2)])
		return dp[n]


class Solution:

	def minOperation(self, n):
		if n == 0:
			return 0
		elif n % 2 == 0:
			return 1 + self.minOperation(n // 2)
		else:
			return 1 + self.minOperation(n - 1)


class Solution:

	def minOperation(self, n):
		dp = [0 for _ in range(n + 1)]
		for i in range(1, n + 1):
			dp[i] = dp[i - 1] + 1
			if not i % 2 and i // 2 >= 0:
				dp[i] = min(dp[i // 2] + 1, dp[i])
		return dp[n]


class Solution:

	def minOperation(self, k):
		dp = [0] * (k + 1)
		for i in range(1, k + 1):
			dp[i] = dp[i - 1] + 1
			if i % 2 == 0:
				dp[i] = min(dp[i], dp[i // 2] + 1)
		return dp[k]


class Solution:

	def minOperation(self, n, memo={}):
		if n in memo:
			return memo[n]
		if n == 1:
			return 1
		s = 0
		if n % 2 == 0:
			s += self.minOperation(n / 2, memo) + 1
		else:
			s += self.minOperation(n - 1, memo) + 1
		memo[n] = s
		return s


class Solution:

	def minOperation(self, n):
		return min_op(n)

def min_op(n):
	if n == 0:
		return 0
	if n % 2 == 0:
		return 1 + min_op(n / 2)
	elif n % 2 != 0:
		return 1 + min_op(n - 1)
	else:
		opt1 = min_op(n / 2)
		opt2 = min_op(n - 1)
		return min(opt1, opt2)


class Solution:

	def minOperation(self, n):
		dp = [0] * (n + 1)
		for i in range(1, n + 1):
			sub = 1 + dp[i - 1]
			div = 9999999999999999
			if i % 2 == 0:
				div = 1 + dp[i // 2]
			dp[i] = min(sub, div)
		return dp[n]


class Solution:

	def minOperation(self, n):
		ans = [1000000 for i in range(n + 1)]
		for i in range(n // 2 + 1, n + 1):
			ans[i] = n - i
		for i in range(n // 2, -1, -1):
			ans[i] = 1 + min(ans[i + 1], ans[2 * i])
		return ans[0]


class Solution:

	def minOperation(self, n):
		(cnt1, ls, b) = (0, 0, 0)
		while n:
			b = n & -n
			n &= ~b
			cnt1 += 1
		if b & 4294901760:
			ls += 16
		if b & 4278255360:
			ls += 8
		if b & 4042322160:
			ls += 4
		if b & 3435973836:
			ls += 2
		if b & 2863311530:
			ls += 1
		return ls + cnt1


class Solution:

	def minOperation(self, n):
		minArr = [None] * (n + 1)
		minArr[0] = 0
		for i in range(1, n + 1):
			if i % 2 != 0:
				minArr[i] = 1 + minArr[i - 1]
			else:
				minArr[i] = 1 + min(minArr[i - 1], minArr[i // 2])
		return minArr[-1]


class Solution:

	def minOperation(self, n):
		ans = 0
		while n > 0:
			if n % 2 == 0:
				n = int(n / 2)
			else:
				n -= 1
			ans += 1
		return ans


class Solution:

	def minOperation(self, n):
		DP = [0 for i in range(n + 1)]
		for i in range(1, n + 1):
			if i % 2 == 0:
				DP[i] = 1 + DP[i // 2]
			else:
				DP[i] = 1 + DP[i - 1]
		return DP[n]


class Solution:

	def minOperation(self, N):
		dp = [-1] * (N + 1)
		dp[0] = 0
		for n in range(1, N + 1):
			add = 9999999
			if n - 1 >= 0:
				add = 1 + dp[n - 1]
			double = 9999999
			if n % 2 == 0:
				double = 1 + dp[int(n / 2)]
			dp[n] = min(add, double)
		return dp[N]


class Solution:

	def minOperation(self, n):
		minOp = [0, 1]
		if n < 2:
			return minOp[n]
		for i in range(2, n + 1):
			if i % 2 != 0:
				minOp.append(minOp[i - 1] + 1)
			else:
				minOp.append(min(minOp[i // 2] + 1, minOp[i - 1] + 1))
		return minOp[n]


from queue import Queue

class Solution:

	def minOperation(self, n):
		if False:
			start = 0
			if n == 0:
				return 0
			if n == 1:
				return 1
			if n == 2:
				return 2
			if n % 2 == 0:
				return self.minOperation(n / 2) + 1
			else:
				return self.minOperation((n - 1) / 2) + 2
		else:
			queue = Queue()
			queue.put(n)
			min_tot = 0
			while not queue.empty():
				curr = queue.get()
				if curr == 0:
					continue
				elif curr == 1:
					min_tot += 1
				elif curr == 2:
					min_tot += 2
				elif curr % 2 == 0:
					queue.put(curr / 2)
					min_tot += 1
				else:
					queue.put((curr - 1) / 2)
					min_tot += 2
			return min_tot


class Solution:

	def minOperation(self, n):
		dp = [0] * (n + 1)
		for i in range(n - 1, 0, -1):
			l = r = float('inf')
			if i * 2 <= n:
				l = dp[i * 2] + 1
			if i + 1 <= n:
				r = dp[i + 1] + 1
			dp[i] = min(l, r)
		return dp[1] + 1


class Solution:

	def minOperation(self, n):
		if n == 0:
			return 0
		cout = 0
		j = n
		while j != 0:
			if j % 2 == 0:
				cout = cout + 1
				j = j // 2
			elif j % 2 != 0:
				cout = cout + 1
				j = j - 1
		return cout


class Solution:

	def minOperation(self, n):
		count = 0
		number_remaining = n
		while number_remaining > 0:
			if number_remaining % 2 == 0:
				number_remaining = int(number_remaining / 2)
			else:
				number_remaining -= 1
			count += 1
		return count


class Solution:

	def minOperation(self, n):
		x = 0
		while n > 0:
			if n % 2:
				x = x + 1
				n = n - 1
			if n == 0:
				break
			n = n / 2
			x = x + 1
		return x


from collections import deque

class Solution:

	def minOperation(self, n):
		q = deque()
		q.append([0, 0])
		visited = set()
		while q:
			(val, count) = q.popleft()
			if val == n:
				return count
			if val not in visited:
				visited.add(val)
				q.append([val + 1, count + 1])
				q.append([val * 2, count + 1])
		return -1


import sys
sys.setrecursionlimit(10 ** 7)

class Solution:

	def WithoutDP(self, n):
		if n <= 1:
			return 1
		if n % 2 != 0:
			return self.WithoutDP(n - 1) + 1
		return self.WithoutDP(n / 2) + 1

	def TopDown(self, n, memory):
		if n <= 1:
			return 1
		if memory[n] == -1:
			if n % 2 != 0:
				memory[n] = self.TopDown(n - 1, memory) + 1
			else:
				memory[n] = self.TopDown(n // 2, memory) + 1
		return memory[n]

	def WithDPTopDown(self, n):
		memory = [-1] * (n + 1)
		return self.TopDown(n, memory)

	def BottomUpDP(self, n):
		memory = [0] * (n + 1)
		memory[0] = 1
		memory[1] = 1
		for i in range(2, n + 1):
			memory[i] = memory[i // 2] + 1 if i % 2 == 0 else memory[i - 1] + 1
		return memory[n]

	def SpaceOptimized(self, n):
		current = 0
		while n != 0:
			n = n // 2 if n % 2 == 0 else n - 1
			current += 1
		return current

	def minOperation(self, n):
		return self.SpaceOptimized(n)


import sys
sys.setrecursionlimit(10 ** 7)

class Solution:

	def WithoutDP(self, n):
		if n <= 1:
			return 1
		if n % 2 != 0:
			return self.WithoutDP(n - 1) + 1
		return self.WithoutDP(n / 2) + 1

	def TopDown(self, n, memory):
		if n <= 1:
			return 1
		if memory[n] == -1:
			if n % 2 != 0:
				memory[n] = self.TopDown(n - 1, memory) + 1
			else:
				memory[n] = self.TopDown(n // 2, memory) + 1
		return memory[n]

	def WithDPTopDown(self, n):
		memory = [-1] * (n + 1)
		return self.TopDown(n, memory)

	def minOperation(self, n):
		return self.WithDPTopDown(n)