Leetcode Integer Replacement problem solution

YASH PAL,

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.
Leetcode Integer Replacement problem solution

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
        visited.add(num)
        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;

}

coding problems