Integer Replacement ( LeetCode ) Problem Solution

Integer Replacement ( LeetCode ) Problem Solution.

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

Solution:-

class Solution:

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

        def sol(n,steps):

            if n==1:

                return steps

            else:

                if(n%2==0):

                    return sol(n//2,steps+1)

                else:

                    return min(sol(n+1,steps+1),sol(n-1,steps+1))

        

        return sol(n,0)

Runtime: 276 ms, faster than 19.50% of Python3 online submissions for Integer Replacement.

Memory Usage: 14 MB, but 100.00% of Python3 online submissions for Integer Replacement.