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.
LeetCode - Integer Replacement Java Solution
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.
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.
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.
- 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