Sponsored
Sponsored
This approach involves converting the number into its binary representation and then finding the positions of '1's. We will iterate through the binary string, keep track of the last position where a '1' was found, and calculate the distance from the current '1' to the last. Record the maximum distance found.
Time Complexity: O(log n) — The number of iterations is proportional to the number of bits, which is log2(n).
Space Complexity: O(1) — Only a few variables are used.
1def binary_gap(n):
2 last_position = -1
3 max_gap = 0
4 idx = 0
5 while n > 0:
6 if n & 1:
7 if last_position != -1:
8 max_gap = max(max_gap, idx - last_position)
9 last_position = idx
10 n >>= 1
11 idx += 1
12 return max_gap
13
14print(binary_gap(22)) # Output: 2We handle the number bit by bit, checking for '1's and calculating the maximum gap with simple bitwise operations.
This approach involves converting the integer to its binary string representation, iterating through the string to find indices of '1's, and calculating and storing the distances between consecutive '1's to find the maximum gap.
Time Complexity: O(log n)
Space Complexity: O(log n) due to storage of binary string.
1#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int binaryGap(int n) {
string binStr = "";
while (n > 0) {
binStr = (char)((n % 2) + '0') + binStr;
n /= 2;
}
int lastPosition = -1, maxGap = 0;
for (int i = 0; i < binStr.length(); ++i) {
if (binStr[i] == '1') {
if (lastPosition != -1) {
maxGap = max(maxGap, i - lastPosition);
}
lastPosition = i;
}
}
return maxGap;
}
int main() {
cout << binaryGap(22) << endl; // Output: 2
return 0;
}Transform 'n' directly to a string representation in binary, iterate over this string to compute gaps between '1's, and determine the max gap.