The Binary Gap is the number of Consecutive zeros in the binary representation of a decimal number surrounded by 1’s at both ends. The Problem of Binary Gap corresponds to finding the longest Binary Gap in a given Decimal number. In programming terms this decimal number is an integer.
For example consider an integer 9 which can be represented as 1001 in binary digits. So here the Binary Gap of 9 will be said to be 2 as there are two consecutive zeros which are surrounded by 1’s at both ends. Similarly the number 41 can be represented in Binary as 101001, so it has two binary gaps but the bigger gap is of length 2. So the binary gap of 41 will be 2.
Another example is decimal number 4 which can be represented as 100 in binary. Although it has 2 consecutive zeros but they are not surrounded by 1’s. Due to this the Binary Gap of 4 is 0 or none.
So the problem is to write a function:
1 | int binaryGap(int N) |
such that when an integer N is passed to it the function returns the Binary Gap in its decimal representation. The function should return 0 in case no binary gap is present.
For example, given N = 41 the function should return 2.
Assumptions are listed Below:
- N is a positive integer with higher limit 2,147,483,647.
Expected complexities:
- Worst-case time complexity should be O(log(N));
- Worst-case space complexity is O(1).
