LeetCode 0397. Integer Replacement Solution in Java, Python, C++, JavaScript, Go & Rust | Explanation + Code

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

PythonJavaC++Go

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)