Highest power of 2 that divides a number represented in binary
Given binary string str, the task is to find the largest power of 2 that divides the decimal equivalent of the given binary number.
Examples:
Input: str = “100100”
Output: 2
22 = 4 is the highest power of 2 that divides 36 (100100).
Input: str = “10010”
Output: 1
Approach: Starting from the right, count the number of 0s in the binary representation which is the highest power of 2 which will divide the number.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the highest power of 2 // which divides the given binary number int highestPower(string str, int len) { // To store the highest required power of 2 int ans = 0; // Counting number of consecutive zeros // from the end in the given binary string for ( int i = len - 1; i >= 0; i--) { if (str[i] == '0' ) ans++; else break ; } return ans; } // Driver code int main() { string str = "100100" ; int len = str.length(); cout << highestPower(str, len); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to return the highest power of 2 // which divides the given binary number static int highestPower(String str, int len) { // To store the highest required power of 2 int ans = 0 ; // Counting number of consecutive zeros // from the end in the given binary string for ( int i = len - 1 ; i >= 0 ; i--) { if (str.charAt(i) == '0' ) ans++; else break ; } return ans; } // Driver code public static void main(String[] args) { String str = "100100" ; int len = str.length(); System.out.println(highestPower(str, len)); } } // This code is contributed by Code_Mech. |
Python3
# Python3 implementation of the approach # Function to return the highest power of 2 # which divides the given binary number def highestPower( str , length): # To store the highest required power of 2 ans = 0 ; # Counting number of consecutive zeros # from the end in the given binary string for i in range (length - 1 , - 1 , - 1 ): if ( str [i] = = '0' ): ans + = 1 ; else : break ; return ans; # Driver code def main(): str = "100100" ; length = len ( str ); print (highestPower( str , length)); if __name__ = = '__main__' : main() # This code contributed by PrinciRaj1992 |
C#
// C# implementation of the approach using System; class GFG { // Function to return the highest power of 2 // which divides the given binary number static int highestPower(String str, int len) { // To store the highest required power of 2 int ans = 0; // Counting number of consecutive zeros // from the end in the given binary string for ( int i = len - 1; i >= 0; i--) { if (str[i] == '0' ) ans++; else break ; } return ans; } // Driver code public static void Main(String[] args) { String str = "100100" ; int len = str.Length; Console.WriteLine(highestPower(str, len)); } } /* This code contributed by PrinciRaj1992 */ |
PHP
<?php // PHP implementation of the approach // Function to return the highest power of 2 // which divides the given binary number function highestPower( $str , $len ) { // To store the highest required power of 2 $ans = 0; // Counting number of consecutive zeros // from the end in the given binary string for ( $i = $len - 1; $i >= 0; $i --) { if ( $str [ $i ] == '0' ) $ans ++; else break ; } return $ans ; } // Driver code $str = "100100" ; $len = strlen ( $str ); echo highestPower( $str , $len ); // This code is contributed by Ryuga ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the highest power of 2 // which divides the given binary number function highestPower(str, len) { // To store the highest required power of 2 let ans = 0; // Counting number of consecutive zeros // from the end in the given binary string for (let i = len - 1; i >= 0; i--) { if (str[i] == '0' ) ans++; else break ; } return ans; } // Driver code let str = "100100" ; let len = str.length; document.write(highestPower(str, len)); </script> |
Output
2
Time Complexity: O(n) where n is number of elements in given array. As, we are using a loop to traverse N times so it will cost us O(N) time
Auxiliary Space: O(1), as we are not using any extra space.
Contact Us