Skip to content

397. Integer Replacement

Description

Given a positive integer n, you can apply one of the following operations:

  1. If n is even, replace n with n / 2.
  2. If n is odd, replace n with either n + 1 or n - 1.

Return the minimum number of operations needed for n to become 1.

 

Example 1:

Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

Example 2:

Input: n = 7
Output: 4
Explanation: 7 -> 8 -> 4 -> 2 -> 1
or 7 -> 6 -> 3 -> 2 -> 1

Example 3:

Input: n = 4
Output: 2

 

Constraints:

  • 1 <= n <= 231 - 1

Solutions

Solution 1

Thinking

Even: divide by \(2\); odd: \(\pm 1\). Minimize steps to \(1\). BFS works; a bit greedy is shorter. Evens must shift; odds with suffix \(11\) (except \(3\)) increment to clear more ones, otherwise decrement.

Treat \(3\) as decrement so we do not go \(3\to 4\). Loop until \(1\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def integerReplacement(self, n: int) -> int:
        ans = 0
        while n != 1:
            if (n & 1) == 0:
                n >>= 1
            elif n != 3 and (n & 3) == 3:
                n += 1
            else:
                n -= 1
            ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int integerReplacement(int n) {
        int ans = 0;
        while (n != 1) {
            if ((n & 1) == 0) {
                n >>>= 1;
            } else if (n != 3 && (n & 3) == 3) {
                ++n;
            } else {
                --n;
            }
            ++ans;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int integerReplacement(int N) {
        int ans = 0;
        long n = N;
        while (n != 1) {
            if ((n & 1) == 0)
                n >>= 1;
            else if (n != 3 && (n & 3) == 3)
                ++n;
            else
                --n;
            ++ans;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func integerReplacement(n int) int {
    ans := 0
    for n != 1 {
        if (n & 1) == 0 {
            n >>= 1
        } else if n != 3 && (n&3) == 3 {
            n++
        } else {
            n--
        }
        ans++
    }
    return ans
}

Comments