Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Build confidence with an intuition-first walkthrough focused on bit manipulation fundamentals.
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 = 8 Output: 0 Explanation: 8 in binary is "1000". There are not any adjacent pairs of 1's in the binary representation of 8, so we return 0.
Example 3:
Input: n = 5 Output: 2 Explanation: 5 in binary is "101".
Constraints:
1 <= n <= 109Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Bit Manipulation
22
8
5
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #868: Binary Gap
class Solution {
public int binaryGap(int n) {
int ans = 0;
for (int pre = 100, cur = 0; n != 0; n >>= 1) {
if (n % 2 == 1) {
ans = Math.max(ans, cur - pre);
pre = cur;
}
++cur;
}
return ans;
}
}
// Accepted solution for LeetCode #868: Binary Gap
func binaryGap(n int) (ans int) {
for pre, cur := 100, 0; n != 0; n >>= 1 {
if n&1 == 1 {
ans = max(ans, cur-pre)
pre = cur
}
cur++
}
return
}
# Accepted solution for LeetCode #868: Binary Gap
class Solution:
def binaryGap(self, n: int) -> int:
ans = 0
pre, cur = inf, 0
while n:
if n & 1:
ans = max(ans, cur - pre)
pre = cur
cur += 1
n >>= 1
return ans
// Accepted solution for LeetCode #868: Binary Gap
impl Solution {
pub fn binary_gap(mut n: i32) -> i32 {
let mut ans = 0;
let mut pre = 100;
let mut cur = 0;
while n != 0 {
if n % 2 == 1 {
ans = ans.max(cur - pre);
pre = cur;
}
cur += 1;
n >>= 1;
}
ans
}
}
// Accepted solution for LeetCode #868: Binary Gap
function binaryGap(n: number): number {
let ans = 0;
for (let pre = 100, cur = 0; n; n >>= 1) {
if (n & 1) {
ans = Math.max(ans, cur - pre);
pre = cur;
}
++cur;
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Sort the array in O(n log n), then scan for the missing or unique element by comparing adjacent pairs. Sorting requires O(n) auxiliary space (or O(1) with in-place sort but O(n log n) time remains). The sort step dominates.
Bitwise operations (AND, OR, XOR, shifts) are O(1) per operation on fixed-width integers. A single pass through the input with bit operations gives O(n) time. The key insight: XOR of a number with itself is 0, which eliminates duplicates without extra space.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.