Last updated on February 3rd, 2025 at 10:47 pm

Here, we see Integer Replacement LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Bit-Manipulation, Math

Companies

Baidu, Google

Level of Question

Medium

Integer Replacement LeetCode Solution

1. Problem Statement

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

• If n is even, replace n with n / 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

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is Dynamic Programming (DP) and Greedy Approach.

• Dynamic Programming (DP): The C++ and Java implementations use memoization to store intermediate results, avoiding redundant calculations. This is a classic DP approach to optimize recursive solutions.
• Greedy Approach: The JavaScript and Python implementations use a greedy approach to decide whether to increment or decrement the number based on specific conditions, aiming to minimize the number of steps.

3. Code Implementation in Different Languages

3.1 Integer Replacement C++

class Solution {
public:
    int integerReplacement(int n) {
        unordered_map<unsigned int,int> dp;
        return solve(dp,n);        
    }

    int solve(unordered_map<unsigned int,int> &dp,unsigned int n){
        if(n==1){
            return 0;
        }
        if(dp.find(n) != dp.end()){
            return dp[n];
        }
        if(n&1){
            return dp[n] = min(solve(dp,n+1),solve(dp,n-1))+1;
        }else{
            return dp[n] = solve(dp,n/2)+1;
        }
    }
};

3.2 Integer Replacement Java

class Solution {
    public int integerReplacement(int n) {
    return replace((long)n);
    }
    
    int replace(long n)
    {
       int ans=0;
        if(n<=1)
        {
            return 0;
        }
        if(n%2==0)
        {
            ans=1+replace(n/2);
        }
        else
        {
            ans=1+Math.min(replace(n+1),replace(n-1));
        }
        return ans;
    }
}

3.3 Integer Replacement JavaScript

var integerReplacement = function(n) {
    let count =0;
    while(n > 1){
        if(n ===3) return count + 2
        if(n % 2 ===0){
            n /= 2;
        }else{
            if(((n+1)/2)%2 === 0) n += 1;
            else n -= 1
        }
        count += 1 
    }
    return count    
};

3.4 Integer Replacement Python

class Solution(object):
    def integerReplacement(self, n):
        cnt = 0
        while n != 1:
            if n % 2 == 0:
                n = n //2
            elif n % 4 == 1 or n == 3:
                n -= 1
            else:
                n += 1
            cnt += 1
        
        return cnt

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(log n)	O(log n)
Java	O(2(log n))	O(log n)
JavaScript	O(log n)	O(1)
Python	O(log n)	O(1)