# Leetcode Integer Replacement problem solution

In this Leetcode Integer Replacement problem solution, you are 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.
3. Return the minimum number of operations needed for n to become 1.

## Problem solution in Python.

```def integerReplacement(self, n: int) -> int:
queue = collections.deque([[n, 0]])
visited = set()
while queue:
num, step = queue.popleft()
if num in visited:
continue
if num == 1:
return step
if num % 2 == 0:
queue.append([num//2, step+1])
else:
queue.extend([[num-1, step+1], [num+1, step+1]])
```

## Problem solution in Java.

```class Solution {
public int integerReplacement(int n) {
return cost(n,0);
}
public int cost(int n, int replacement){
if(n<0) n=Math.abs(n); //this is to take care of Integer overflow
if(n==1) return replacement;
if(n==2) return cost(1,replacement+1);
if(n%2==0) {
n=n/2;
return cost(n,replacement+1);
}
else{
return Math.min(cost(n+1,replacement+1),cost(n-1,replacement+1));
}
}
}
```

## Problem solution in C++.

```class Solution {

public:

int integerReplacement(long long n) {

int step=0;
while(n%2==0){
n/=2;
step++;
}
if(n==1) return step;
return min(integerReplacement(n+1)+step+1,integerReplacement(n-1)+step+1);
}
};
```

## Problem solution in C.

```int integerReplacement(long long int n){
int x=0;
while(n!=1){
if (n%2==0){
n=n/2;
}
else if (n==3){
n=n-1;
}
else if((n&3)==3){
n=n+1;
}
else if ((n&3)==1){
n=n-1;
}
x+=1;
}
return x;

}
```