Binary Gap

Problem Description

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.

Key Insights

• The binary representation of the number is crucial to solving the problem.
• The goal is to find pairs of adjacent 1's, which means identifying the positions of 1's in the binary string.
• The distance between adjacent 1's is calculated based on their positions, and we need to keep track of the maximum distance found.

Space and Time Complexity

Time Complexity: O(log n) - The time complexity is determined by the number of bits in the binary representation of n, which is logarithmic relative to n. Space Complexity: O(1) - The solution uses a constant amount of space, regardless of the input size.

Solution

To solve the problem, we can use the following approach:

1. Convert the integer n to its binary representation.
2. Iterate through the binary string to find the indices of 1's.
3. Calculate the distance between adjacent 1's and keep track of the maximum distance found.
4. Return the maximum distance, or 0 if no adjacent 1's are found.

Code Solutions