**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**

- There is subtle trick in this problem that allows us to choose either x-1 or x+1 when x is odd. Say x is 7. Then x-1 = 6 and x+1 = 8. 6/2 = 3 and 8/2=4. Now this is consistent - either (x-1)/2 is even or (x+1)/2 is even. And we want to pick the path that leads us to an even number to reach our goal fastest. One exception is x = 3 where both (x-1)/2 is odd or (x+1)/2 is even. For this case, use x-1 which takes us to 2.
- https://discuss.leetcode.com/topic/58425/java-12-line-4-5-ms-iterative-solution-with-explanations-no-other-data-structures

```
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
```