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.
Examples
Example 1:
|
|
Example 2:
|
|
Example 3:
|
|
Solution
The task is to determine the longest distance between any two adjacent 1’s in the binary representation of a given positive integer ( n ).
Method 1 - Using Binary String
Here is the approach we can take:
- Convert
n
to Binary: Obtain the binary representation ofn
. - Track Positions of
1
s: Iterate through the binary string and record the positions of each1
. - Calculate Distances: Compute the distances between consecutive
1
s and keep track of the maximum distance encountered. - Return Result: If fewer than two
1
s are found, return 0. Otherwise, return the maximum distance.
Code
|
|
Complexity
- Time:
O(log n)
for converting numbern
to binary string - Space:
O(1)