### Integer Replacement LeetCode Solution - The Coding Shala

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

## Integer Replacement Problem

- If n is even, replace n with n / 2.
- If n is odd, replace n with either n + 1 or n - 1.

**Example 1:**

**Example 2:**

## 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:

**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

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**

- LeetCode - Prime Number of Set Bits in Binary Representation
- LeetCode - Number Complement
- LeetCode - Flipping an Image
- LeetCode - Split a String in Balanced Strings
- LeetCode - Range Sum Query Immutable

## Comments

## Post a Comment