class Solution(object):
memo = {}
memo[1] = 0
def integerReplacement(self, n):
"""
:type n: int
:rtype: int
"""
if n in self.memo:
return self.memo[n]
if n & 1 == 1:
ans = 1 + min(self.integerReplacement(n 1), self.integerReplacement(n+1))
else:
ans = 1 + self.integerReplacement(n >> 1)
self.memo[n] = ans
return ans
Python, O(logn) time, O(logn) space, memoization approach


How can we calculate this complexity as
O(logn)
?Even if we use
memo
, theoretically we need to check all0
,1
combination of the integer lengthn
, so at worst case this isO(2^n)
.
But obviously the actual number is less that that becausen  1
is guaranteed to be even, so I'm wondering how we can calculate the accurate complexity of this approach.