MYCP1 : Find Largest power of 2 a Binary number is Divisible

Photo by Chris Liverani on Unsplash

This problem is little bit tricky and easy if you are good at MATH.

Suppose you are given a random binary number 11010 and you need to calculate what is the largest power of 2 to divide this binary number.

11010 in decimal is 26 and this number is divisible by 2⁰, 2¹. So answer is 2¹ means 1.

You can use brute force approach. In which, firstly convert binary to decimal.

Now let us take another solution, Binary number is made of 2^n; where 0 ≤ n ≤ Infinity.

Let us take decimal 10 which is denoted as 1010 also denoted as 2¹ + 2³. Let us take some common outside so 2¹(1+2²). So, It is divisible by 2¹ which tends to answer 1.

It means what is the last-Position of 1 Or How many zeros at the end of the Number gives the answer.

Benefits:

1. Don’t require to convert into Decimal
2. If you know that the number of zeros at the end of the binary is the maximum power of 2 can divide the number, you can do many interesting problem like : “ You are given a number in binary and you can permute bits of number but find what is max power of 2 which can divide the number”

Here is the solution of number-Of-Zero’s Method:

Now you can try this for Permutation type of Question where you need to find only number Of Zero in the String of Number which is in the Binary.

If you are able to do it then try cyclic rotation and find maximum power of two. That’s it for the today..!!!