Convert Binary Number To One


Given a binary string S, the task is to print the numbers of steps required to convert it to one by the following operations:
If S is odd add 1 to it.
If S is even divide it by 2.

Example:
Input: S = “101110”
Output: 8
Number ‘101110’ is even, after dividing it by 2 we get an odd number ‘10111’ so we will add 1 to it. Then we’ll get ‘11000’ which is even and can be divide three times continuously in a row and get ’11’ which is odd, adding 1 to it will give us ‘100’ which is even and can be divided 2 times in a row. As, a result we get 1.
So we had to do any of the above two operations 8 times to reach 1 from the given binary number..

Solution:

Let's take some examples and see how it works: 
101110
 |
 |    /2
 v
10111
 |
 |    +1
 v
11000
 |
 |    /2
 v
1100
 |
 |    /2
 v
110
 |
 |    /2
 v
 11
 |
 |    +1
 v
100
 |
 |    /2
 v
10
 |
 |    /2
 v
 1

Few observations here:
  • When we divide an even number we actually do a right shift. Which means each division will remove the right-most trailing zero.
    So, given an even number how many times can we go on doing division by 2 ? As many trailing (right-most) zeroes we have. In the above example see how when we got 11000 it gets reduced to 11 by doing division by 2 every time, ultimately making it an odd number. So when we have an even number we would take as many steps as there are trailing zero and reduce the number to a number without the trailing zeroes. So 11000 reduces to 11. Basically each time we encounter an even number we remove the right-most 0 from the binary number.
  • When we have ood number we add one to it. Let's see how it works:

    111011 + 1 = 111100
    11000011 + 1 = 11000100
    10001 + 1 = 10010
    11 + 1 = 100

    Did you see a pattern here? Adding one to an odd number toggles all the trailing ones (by toggle I mean convert all the trailing ones to zeroes) and converts the first zero from right to one, keeping all other left digits the same.

    Interesting to see how 11 is converted to 100 by addition of one. It still follows the observation described above.

    So when we encounter an odd number, we could combine these steps: combine addition of one and then required number of division by 2.


Java Code:



Please subscribe to access the complete working solution.



Python Code:



Please subscribe to access the complete working solution.




Related Chapter:

Instructor:

Abhishek Dey

Abhishek Dey

Senior SDE | Chief Architect

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.


Help Your Friends save 40% on our products

wave