Integer Replacement LeetCode Solution - The Coding Shala

Home >> LeetCode >> Integer Replacement

 In this post, we will learn how to solve LeetCode's Integer Replacement Problem and will implement its solution in Java.

Integer Replacement Problem

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.

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

Practice this problem on LeetCode.

LeetCode - Integer Replacement Java Solution

Approach 1

Using Bit Manipulation.

If n is even then the operation is fixed. If n is odd then we have two operations +1 or -1, so for this let's check the binary of the number. We need to check only the second bit of the number. (from right side)

Case 1. If the second bit is 1, then n+1 will remove the minimum of two 1 bits or more and n-1 will remove only one 1.

for example:

n = 1011 + 1 = 1100
n = 1011 - 1 = 1010

Case 2. If the second bit is 0 then n+1 will remove 1 bit and add one bit at the second position bit n-1 will remove 1 bit.

for example 

n = 1001 + 1 = 1010
n= 1001 - 1 = 1001

so base on the second bit we can decide if we have to do +1 or -1.

Special case: for n = 3 there are only 2 steps.

Java Program: 

class Solution {
    public int integerReplacement(int n) {
        if(n == Integer.MAX_VALUE) return 32;
        int res = 0;
        while(n > 1) {
            if(n%2 == 0) {
                n /= 2;
            } else {
                //n=3 special case
                if(n==3) {
                    res = res+2;
                    break;
                }
                
                if((n & 2) == 2) n = n+1;
                else n = n-1;
            }
            res++;
        }
        return res;
    }
}


Other Posts You May Like
Please leave a comment below if you like this post or found some errors, it will help me to improve my content.

Comments

Popular Posts from this Blog

Basic Structure of C++ Program - The Coding Shala

Richest Customer Wealth LeetCode Solution - The Coding Shala

Shell Script to find sum, product and average of given numbers - The Coding Shala

Shell Script to Create a Simple Calculator - The Coding Shala

First Unique Character in a String Java - The Coding Shala