Last updated on October 5th, 2024 at 05:50 pm

Here, We see Integer Replacement LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Integer Replacement LeetCode Solution

Problem Statement

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

1. Integer Replacement LeetCode Solution 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;
        }
    }
};

2. Integer Replacement LeetCode Solution 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. Integer Replacement Solution 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    
};

4. Integer Replacement Solution 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