Given a positive integer n and you can do operations as follow:




If n is even, replace n with n/2.
If n is odd, you can replace n with either n + 1 or n - 1.




What is the minimum number of replacements needed for n to become 1?




Example 1:

Input:
8

Output:
3

Explanation:
8 -> 4 -> 2 -> 1



Example 2:

Input:
7

Output:
4

Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Bit manipulation

Greedy algorithms

Starter code: class Solution:
    def integerReplacement(self, n: int) -> int:
        

Solutions:
class Solution:

	def integerReplacement(self, n):
		ans = 0
		while n > 1:
			if n % 2 == 0:
				n = n // 2
			elif n % 4 == 1 or n == 3:
				n -= 1
			else:
				n += 1
			ans += 1
		return ans


class Solution:

	def integerReplacement(self, n):
		variants = [n]
		nsteps = 0
		seen = set()
		while True:
			n = len(variants)
			for i in range(n):
				v = variants[i]
				if v == 1:
					return nsteps
				if v % 2 == 0:
					x = v // 2
					if x in seen:
						variants[i] = 0
					else:
						variants[i] = x
						seen.add(x)
				else:
					for x in (v - 1, v + 1):
						if x not in seen:
							variants.append(x)
							seen.add(x)
			nsteps += 1


class Solution:

	def integerReplacement(self, n):

		def dfs(n):
			if n == 1:
				return 0
			if n == 3:
				return 2
			if n & 1 == 0:
				return dfs(n >> 1) + 1
			elif n >> 1 & 1 == 0:
				return dfs(n - 1) + 1
			else:
				return dfs(n + 1) + 1
		return dfs(n)


class Solution:

	def integerReplacement(self, n):
		return self.integerReplacementDP(n)
		if n == 1:
			return 0
		if n % 2 == 0:
			return 1 + self.integerReplacement(n / 2)
		else:
			return 1 + min(self.integerReplacement(n + 1), self.integerReplacement(n - 1))

	def integerReplacementDP(self, n, dp=None):
		if dp is None:
			dp = {}
		if n == 1:
			return 0
		if n not in dp:
			if n % 2 == 0:
				dp[n] = 1 + self.integerReplacementDP(n / 2, dp=dp)
			else:
				dp[n] = 1 + min(self.integerReplacementDP(n + 1, dp=dp), self.integerReplacementDP(n - 1, dp=dp))
		return dp[n]

	def integerReplacementBitwise(self, n):
		count = 0
		while n != 1:
			if n & 1 == 0:
				n >>= 1
			elif n == 3 or bin(n + 1).count('1') > bin(n - 1).count('1'):
				n -= 1
			else:
				n += 1
			count += 1
		return count


class Solution:

	def Is2(self, n):
		root = int(math.log(n, 2))
		return 2 ** root == n

	def GetNear2(self, n):
		if n == 0:
			return -1
		if n == 1:
			return 0
		if n == 2:
			return 1
		if self.Is2(n):
			return n
		for ind in range(n - 1, n + 2):
			if self.Is2(ind):
				return ind
		return -1

	def integerReplacement(self, n):
		m = n
		cnt = 0
		while m != 1:
			if m == 1:
				return cnt
			if m == 2:
				return 1 + cnt
			if m <= 4:
				return 2 + cnt
			if m <= 6:
				return 3 + cnt
			if m % 2 == 0:
				cnt += 1
				m = int(m / 2)
				continue
			k = m % 4
			if k == 1:
				cnt += 1
				m = int(m - 1)
			elif k == 3:
				cnt += 1
				m = int(m + 1)
		return cnt


class Solution:

	def integerReplacement(self, n):
		steps = 0
		while n > 1:
			if n & 1 == 0:
				n >>= 1
				steps += 1
			else:
				if n == 3:
					n -= 1
				else:
					n += 1 if n & 2 else -1
				n >>= 1
				steps += 2
		return steps


class Solution:

	def integerReplacement(self, n):
		table = {}

		def helper(i):
			if i == 1:
				return 0
			if i in table:
				return table[i]
			if i % 2 == 0:
				return helper(i // 2) + 1
			table[i] = min(helper(i + 1), helper(i - 1)) + 1
			return table[i]
		return helper(n)


class Solution:

	def integerReplacement(self, n):
		queue = collections.deque([n])
		step = 0
		while len(queue):
			sz = len(queue)
			while sz > 0:
				sz -= 1
				num = queue.popleft()
				if num == 1:
					return step
				if num & 1:
					queue.append(num + 1)
					queue.append(num - 1)
				else:
					queue.append(num // 2)
			step += 1
		return step