Integer Replacement

Problem Id: 397 Difficulty: Medium


Intuition

Solution


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