```
class Solution(object):
def integerReplacement(self, n):
"""
:type n: int
:rtype: int
"""
stack = []
dic = {}
stack.append(n)
dic[n] = 0
while stack.__len__() > 0:
cur = stack.pop()
while cur > 1:
if cur % 2 == 0:
if (cur/2 in dic) and (dic[cur] + 1 >= dic[cur/2]):
break
dic[cur/2] = dic[cur] + 1
cur = cur / 2
else:
if not (cur+1 in stack):
stack.append(cur+1)
dic[cur+1] = dic[cur] + 1
if (cur-1 in dic) and (dic[cur] + 1 >= dic[cur-1]):
break
dic[cur-1] = dic[cur] + 1
cur = cur - 1
return dic[1]
```