Python solution with detailed explanation

• Solution

Integer Replacement https://leetcode.com/problems/integer-replacement/

BFS Based Solution

• We can use a simple BFS solution here.
``````from Queue import Queue
class Solution2(object):
def integerReplacement(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 1:
return 0
q = Queue()
q.put(n)
levels = -1
while q.empty() == False:
N = q.qsize()
levels += 1
for i in range(N):
x = q.get()
if x & 1 == 0:
y = x >> 1
if y == 1:
return levels + 1
else:
q.put(y)
else:
y1, y2 = x-1, x+1
if y1 == 1:
return levels + 1
else:
q.put(y1)
q.put(y2)
return
``````

Optimized Solution

``````class Solution(object):
def integerReplacement(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 1:
return 0
level = 0
while n != 1:
if n & 1 == 0:
n, level = n / 2, level + 1
elif n == 3:
n, level = n-1, level + 1
else:
if (n-1)/2 & 1 == 0:
n, level = n-1, level + 1
else:
n, level = n+1, level + 1
return level
``````

• @gabbu , I have rewritten your integer optimized solution to the following. You can increment the level in the end , instead of doing it in every if-else branch.

``````count = 0
while n != 1:
if n %2 == 0:
n = n / 2
elif n == 3:
n = n - 1
else:
if (n-1)/2 % 2 == 0:
n = n - 1
else:
n = n + 1
count += 1
return count
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.