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

Difficulty: interview

Starter code:

class Solution:
    def integerReplacement(self, n: int) -> int:
        

Solutions:
class Solution:
     def integerReplacement(self, n):
         """
         :type n: int
         :rtype: int
         """
         '''
         if n == 1:
             return 0
         if not (n & 1):
             return self.integerReplacement(n//2) + 1
         return min(self.integerReplacement(n+1), self.integerReplacement(n-1)) + 1
         '''
         ans = 0
         while n > 1:
             if n % 2 == 0:
                 n = n // 2
             elif n % 4 == 1 or n == 3:
                 n -= 1
             else:
                 n += 1
             ans += 1
         return ans


class Solution:
     def integerReplacement(self, n):
         """
         :type n: int
         :rtype: int
         """
         variants = [n]
         nsteps = 0
         seen = set()
         
         while True:
             n = len(variants)
             for i in range(n):
                 v = variants[i]
                 if v == 1:
                     return nsteps
                 
                 if v % 2 == 0:
                     x = v // 2
                     if x in seen:
                         variants[i] = 0
                     else:
                         variants[i] = x
                         seen.add(x)
                 else:
                     for x in v-1, v+1:
                         if x not in seen:
                             variants.append(x)
                             seen.add(x)
                     
             nsteps += 1


class Solution:
     def integerReplacement(self, n):
         """
         :type n: int
         :rtype: int
         """
         def dfs(n):
             if n==1: return 0
             if n==3: return 2
             if (n & 0x1)==0: return dfs(n>>1)+1
             elif ((n>>1) & 0x1)==0: return dfs(n-1)+1
             else: return dfs(n+1)+1
             
         return dfs(n)

class Solution:
     def integerReplacement(self, n):
         """
         :type n: int
         :rtype: int
         """
         return self.integerReplacementDP(n)
         # return self.integerReplacementBitwise(n)
         if n == 1:
             return 0
 
         if n % 2 == 0:
             return 1 + self.integerReplacement(n / 2)
         else:
             return 1 + min(self.integerReplacement(n + 1), self.integerReplacement(n - 1))
         
     def integerReplacementDP(self, n, dp=None):
         if dp is None:
             dp = {}
             
         if n == 1:
             return 0
         
         if n not in dp:
             if n % 2 == 0:
                 dp[n] = 1 + self.integerReplacementDP(n / 2, dp=dp)
             else:
                 dp[n] = 1 + min(self.integerReplacementDP(n + 1, dp=dp), self.integerReplacementDP(n - 1, dp=dp))
         return dp[n]
 
     def integerReplacementBitwise(self, n):
         """
         
         5 -> 4 -> 2 -> 1
         5 -> 6 -> 3 -> 2 -> 1
         
         101 100
         101 110   
         
         11 10
         """
         
         count = 0
         while n != 1:
             if (n & 1) == 0:
                 n >>= 1
             elif n == 3 or bin(n + 1).count('1') > bin(n - 1).count('1'):
                 n -= 1
             else:
                 n += 1
             count += 1
 
         return count


class Solution:
     def Is2(self, n):
         root = int(math.log(n, 2))
         return (2**root) == n
     def GetNear2(self, n):
         if n == 0:
             return -1
         if n == 1:
             return 0
         if n == 2:
             return 1
         if self.Is2(n):
             return n
         for ind in range(n - 1, n + 2):
             if self.Is2(ind):
                 return ind
         return -1
     def integerReplacement(self, n):
         """
         :type n: int
         :rtype: int
         """
 
         m = n
         cnt = 0
         while m != 1:
             if m == 1:
                 return cnt
             if m == 2:
                 return 1 + cnt
             if m <= 4:
                 return 2 + cnt
             if m <= 6:
                 return 3 + cnt
             if m % 2 == 0:
                 cnt += 1
                 m = int(m / 2)
                 continue
             k = m % 4
             if k == 1:
                 cnt += 1
                 m = int(m - 1)
             elif k == 3:
                 cnt += 1
                 m = int(m + 1)
             
         return cnt


class Solution:
     def integerReplacement(self, n):
         """
         :type n: int
         :rtype: int
         """
         steps = 0
         while n > 1:
             if n&1 == 0:
                 n >>= 1
                 steps += 1
             else:
                 if n == 3:
                     n -= 1
                 else:
                     n += 1 if n&2 else -1
                 n >>= 1
                 steps += 2
         return steps

class Solution:
     def integerReplacement(self, n):
         """
         :type n: int
         :rtype: int
         """
         table = {}
         def helper(i):
             if i == 1:
                 return 0
             if i in table:
                 return table[i]
             if i % 2 == 0:
                 return helper(i // 2) + 1
             table[i] = min(helper(i+1), helper(i-1)) + 1
             return table[i]
         return helper(n)


class Solution:
     def integerReplacement(self, n):
         """
         :type n: int
         :rtype: int
         """
         queue = collections.deque([n])
         step = 0
         while len(queue):
             sz = len(queue)
             while sz > 0:
                 sz -= 1
                 num = queue.popleft()
                 if num == 1:
                     return step
                 if num & 1:
                     queue.append(num + 1)
                     queue.append(num - 1)
                 else:
                     queue.append(num // 2)
             step += 1
         return step