In this Leetcode Integer Replacement problem solution, you are given a positive integer n, you can apply one of the following operations:
- If n is even, replace n with n / 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.
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; }
1 Comments
This comment has been removed by the author.
ReplyDelete