Python solution with detailed explanation


  • 0
    G

    Solution

    Integer Replacement https://leetcode.com/problems/integer-replacement/

    BFS Based Solution

    • We can use a simple BFS solution here.
    from Queue import Queue
    class Solution2(object):
        def integerReplacement(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n <= 1:
                return 0
            q = Queue()
            q.put(n)
            levels = -1
            while q.empty() == False:
                N = q.qsize()
                levels += 1
                for i in range(N):
                    x = q.get()
                    if x & 1 == 0:
                        y = x >> 1
                        if y == 1:
                            return levels + 1
                        else:
                            q.put(y)
                    else:
                        y1, y2 = x-1, x+1
                        if y1 == 1:
                            return levels + 1
                        else:
                            q.put(y1)
                            q.put(y2)
            return   
    

    Optimized Solution

    class Solution(object):
        def integerReplacement(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n <= 1:
                return 0
            level = 0
            while n != 1:
                if n & 1 == 0:
                    n, level = n / 2, level + 1
                elif n == 3:
                    n, level = n-1, level + 1
                else:
                    if (n-1)/2 & 1 == 0:
                        n, level = n-1, level + 1
                    else:
                        n, level = n+1, level + 1                    
            return level
    

  • 0
    R

    @gabbu , I have rewritten your integer optimized solution to the following. You can increment the level in the end , instead of doing it in every if-else branch.

    count = 0
            while n != 1:
                if n %2 == 0:
                    n = n / 2 
                elif n == 3:
                    n = n - 1
                else:
                    if (n-1)/2 % 2 == 0:
                        n = n - 1
                    else:
                        n = n + 1
                count += 1
            return count
    

Log in to reply
 

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