Binary Gap Problem & Solution
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.
See the binary gap problem on LeetCode.
C++ Solution
#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops")
static const int _=[](){std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();
class Solution {
public:
int binaryGap(int n) {
string s;
while (n > 0) {
s += n % 2 + '0';
n /= 2;
}
int best = 0;
int low = -1;
int high = 0;
while (high < s.size()) {
if (s[high] == '1') {
if (low != -1) {
best = max(best, high - low);
}
low = high;
}
++high;
}
return best;
}
};
Sample Search Queries
Many Paths. Follow Yours.