Algorithm

Problem Name: 397. Integer Replacement

Problem Link: https://leetcode.com/problems/integer-replacement/
 

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

Code Examples

#1 Code Example with C Programming

Code - C Programming


int integerReplacement(int n) {
    int k = 0;
    while (n != 1) {
        if (n & 1) {
            if ((n & 3) == 3 && n > 3) {
                n += 1;
            } else {
                n -= 1;
            }
        } else {
            n = (n >> 1) & 0x7fffffff;
        }
        k ++;
    }
    return k;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
n = 8

Output

x
–
+
cmd
3

#2 Code Example with Javascript Programming

Code - Javascript Programming


const integerReplacement = function(n, memo = {}) {
    if (n === 1) return 0;
    if (memo[n]) return memo[n];
    memo[n] = n % 2 === 0 ? integerReplacement(n/2, memo) + 1 : Math.min(integerReplacement(n+1, memo), integerReplacement(n-1, memo)) + 1;
    return memo[n]; 
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
n = 8

Output

x
–
+
cmd
3

#3 Code Example with Python Programming

Code - Python Programming


class Solution:
    def integerReplacement(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1: 
            return 0
        elif n % 2 == 0: 
            return self.integerReplacement(n/2)+1
        else: 
            return min(self.integerReplacement(n+1),self.integerReplacement(n-1))+1
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
n = 7

Output

x
–
+
cmd
4
Advertisements

Demonstration

Previous
#396 Leetcode Rotate Function Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#398 Leetcode Random Pick Index Solution in C, C++, Java, JavaScript, Python, C# Leetcode