Number Of Steps To Reduce A Number In Binary Representation To One - Leetcode Solution

Problem Statement:

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. Return the minimum number of operations needed to reduce N to 1.

Example 1: Input: N = 14 Output: 6 Explanation: Binary representation of 14 is 1110. Step 1, convert 2nd digit from right to 0, the number becomes 1100 (decimal 12) Step 2, convert 3rd digit from right to 0, the number becomes 1000 (decimal 8) Step 3, convert 4th digit from right to 0, the number becomes 0b100 (decimal 4) Step 4, convert 3rd digit from right to 1, the number becomes 0b101 (decimal 5) Step 5, convert 2nd digit from right to 0, the number becomes 0b100 (decimal 4) Step 6, convert 2nd digit from right to 1, the number becomes 0b101 (decimal 5). Both numbers are represented in binary as 101.

Example 2: Input: N = 8 Output: 3 Explanation: Binary representation of 8 is 1000. Step 1, convert 2nd digit from right to 0, the number becomes 0b100 (decimal 4) Step 2, convert 2nd digit from right to 1, the number becomes 0b101 (decimal 5) Step 3, convert 2nd digit from right to 0, the number becomes 0b100 (decimal 4).

Solution:

Approach:

1. We iterate through the binary representation of the given number N, starting from the least significant bit (rightmost bit) to the most significant bit (leftmost bit).
2. If we encounter a '0', we divide the number by 2 to make the bit 0.
3. If we encounter a '1', we add one to the count of steps required to convert the number to 1.
4. If we have consecutive '1's, we set the least significant bit to '0' and all the bits to the right of it to '0' too. This operation will reduce the number by a power of 2 and is equivalent to the operation of dividing the number by 2 multiple times.
5. Return the count of steps required to convert the number to 1 after performing the above-mentioned operations.

Algorithm:

1. Initialize a variable 'steps' as 0 to keep count of steps required to reduce the number to 1.
2. While N is greater than 1, perform the following steps: a) If the last bit of N is 0, divide N by 2. b) If the last bit of N is 1, increment steps by 1 and check if the second to last bit is also 1. i) If the second to last bit is 1, set the last two bits of N to '0' and divide N by 2. ii) If the second to last bit is 0, set the last bit of N to '0' and divide N by 2.
3. Return steps+1, as one step is required to reduce N to 1.

Code:

// Java Code class Solution { public int numSteps(String s) { int steps = 0; int carry = 0; int n = s.length(); for(int i=n-1;i>0;i--){ int curr = s.charAt(i)-'0'; if(curr+carry==1){ carry=1; steps+=2; } if(curr+carry==2){ steps+=1; } } if(carry==0) return steps+1; return steps+n; } }

// Python Code class Solution(object): def numSteps(self, s): """ :type s: str :rtype: int """ steps=0 carry=0 n=len(s) for i in range(n-1,0,-1): curr=int(s[i]) if curr+carry==1: carry=1 steps+=2 if curr+carry==2: steps+=1 if carry==0: return steps+1 return steps+n

1