# Time: O(logn) # Space: O(1) # Given a positive integer n and you can do operations as follow: # # If n is even, replace n with n/2. # If n is odd, you can replace n with either n + 1 or n - 1. # What is the minimum number of replacements needed for n to become 1? # # Example 1: # # Input: # 8 # # Output: # 3 # # Explanation: # 8 -> 4 -> 2 -> 1 # Example 2: # # Input: # 7 # # Output: # 4 # # Explanation: # 7 -> 8 -> 4 -> 2 -> 1 # or # 7 -> 6 -> 3 -> 2 -> 1 # Iterative solution. class Solution(object): def integerReplacement(self, n): """ :type n: int :rtype: int """ result = 0 while n != 1: b = n & 3 if n == 3: n -= 1 elif b == 3: n += 1 elif b == 1: n -= 1 else: n /= 2 result += 1 return result # Time: O(logn) # Space: O(logn) # Recursive solution. class Solution2(object): def integerReplacement(self, n): """ :type n: int :rtype: int """ if n < 4: return [0, 0, 1, 2][n] if n % 4 in (0, 2): return self.integerReplacement(n / 2) + 1 elif n % 4 == 1: return self.integerReplacement((n - 1) / 4) + 3 else: return self.integerReplacement((n + 1) / 4) + 3