Python, O(logn) time, O(logn) space, memoization approach


  • 0
    A
    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
            
                
    

  • 0

    How can we calculate this complexity as O(logn) ?

    Even if we use memo, theoretically we need to check all 0, 1 combination of the integer length n, so at worst case this is O(2^n).
    But obviously the actual number is less that that because n - 1 is guaranteed to be even, so I'm wondering how we can calculate the accurate complexity of this approach.


Log in to reply
 

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