[Leet Code] Binary Gap

Leet code: https://leetcode.com/problems/binary-gap/

Problem:

Given a positive integer n, find and return the longest distance between any two adjacent 1's in the binary representation of n. If there are no two adjacent 1's, return 0.

Two 1's are adjacent if there are only 0's separating them (possibly no 0's). The distance between two 1's is the absolute difference between their bit positions. For example, the two 1's in "1001" have a distance of 3.

Example 1:

Input: n = 22
Output: 2
Explanation: 22 in binary is "10110".
The first adjacent pair of 1's is "10110" with a distance of 2.
The second adjacent pair of 1's is "10110" with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that "10110" is not a valid pair since there is a 1 separating the two 1's underlined.

Example 2:

Input: n = 5
Output: 2
Explanation: 5 in binary is "101".

Example 3:

Input: n = 6
Output: 1
Explanation: 6 in binary is "110".

Example 4:

Input: n = 8
Output: 0
Explanation: 8 in binary is "1000".
There aren't any adjacent pairs of 1's in the binary representation of 8, so we return 0.

Example 5:

Input: n = 1
Output: 0

Constraints:

• 1 <= n <= 109

Solution:

class Solution(object):
    def binaryGap(self, n):
        """
        :type n: int
        :rtype: int
        """
        binary = format(n, "b")
        highest_num = 0
        num_counter = 0
        while num_counter < len(binary):
            if binary[num_counter] == "1":
                counter = 0
                for i in range(num_counter+1, len(binary)):
                    counter += 1
                    if binary[i] == "1":
                        if counter > highest_num: 
                            highest_num = counter
                        num_counter = i-1 
                        break
            num_counter += 1
                        
        return highest_num

Explanation:

This is not the most optimised solution, but a solution nonetheless. So first we want to get the binary representation of the integer number we’re given. binary = format(n, "b") then we want to make some variables, one being the highest_num and the second being num_counter. Num_counter will be used to go through our binary representation character by character in the while loop. In the while loop, we want to check if the character we’re currently on is a 1, if so, we want to initalise a counter variable to keep track of how many 0s are inbetween this 1 and the next 1, if it exists. Then we do a for loop, starting at the character after the 1 we’ve just discovered at the start of the while loop, and ending at the length of the binary representation + 1 due to lists being 0-indexed. We count 1, and then we check if there is another one while we’re in the for loop. If there isn’t, it will continue through the for loop, and continue to increment the counter. If there is no other 1 found, then nothing will be assigned to the highest_num variable, and so it will return 0, as the question has asked. However, if we do find another 1 along the way, it will check if the counter variable is higher than the current highest_num variable, and if so, it will assign the value of counter to the variable highest_num. Then we will set the num_counter to i-1 as we then increment the num_counter, outside of the if statement.