```
class Solution(object):
def integerReplacement(self, n):
"""
:type n: int
:rtype: int
"""
def helper(n, mem):
if n in mem.keys():
return mem[n]
m, cnt = n, 0
while n % 2 == 0:
n //= 2
cnt += 1
if n == 1:
mem[m] = cnt
return cnt
mem[m] = 1 + cnt + min(helper(n+1, mem), helper(n-1, mem))
return mem[m]
mem = {1: 0}
return helper(n, mem)
```