# Integer Replacement LeetCode Solution

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

## 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

## 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;
}
}
};```Code language: PHP (php)```

## 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;
}
}```Code language: JavaScript (javascript)```

## 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
};```Code language: JavaScript (javascript)```

## 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``````
Scroll to Top