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
Table of Contents
Problem Statement
Given a positive integer n
, you can apply one of the following operations:
- If
n
is even, replacen
withn / 2
. - If
n
is odd, replacen
with eithern + 1
orn - 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