868. Binary Gap
Problem Description
The problem requires calculating the longest distance between any two adjacent 1
s in the binary representation of a given positive integer n
. In binary terms, adjacent 1
s are those with only 0
s or no 0
in between. The distance is measured by counting the number of bit positions between the two 1
s. If no two adjacent 1
s are found, the function should return 0
.
Intuition
To solve this problem, we need to inspect the binary representation of the number from the least significant bit (LSB) to the most significant bit (MSB). As we iterate through the binary bits, we keep track of the position of the most recent 1
encountered. Every time we find a new 1
, we compute the distance to the previous 1
(if there is one) and update our answer to be the maximum distance found so far.
The intuition behind the provided solution approach is as follows:
- We iterate over 32 bits because an integer in most systems is represented using 32 bits.
- At each bit position
i
, we check if the least significant bit is1
by performing an "AND" operation with1
(n & 1
). - If we encounter a
1
, we check if there is a previous1
(indicated byj != -1
). If there is, we calculate the distance between the current1
(i
) and the previous1
(j
), then update the result (ans
) with the maximum distance found so far. - We record the current bit position
i
as the new previous1
position by settingj = i
. - After each iteration, we right-shift the number (
n >>= 1
) to check the next bit in the following iteration. - We continue this process until all bits have been checked.
- The variable
ans
maintains the longest distance, which is returned at the end of the function.
Solution Approach
The solution employs a straightforward approach that leverages bitwise operations to iterate through each bit of the integer's binary representation. No additional data structures are necessary, and the algorithm follows these steps:
-
Initialize two variables:
ans
to store the longest distance found so far (initially set to zero), andj
to keep track of the position of the last1
encountered (initialized to -1 as no1
has been encountered yet). -
Loop 32 times, which corresponds to the maximum number of bits required to represent an integer in binary (as most modern architectures use 32 bits for standard integers).
-
For each bit position
i
from 0 to 31:- Check if the least significant bit of
n
is1
. This is done using a bitwise AND operation (n & 1
). If the result is not zero, the least significant bit is a1
. - If
j
is not-1
(which means we've found a previous1
), calculate the distance from the current1
to the previous1
by subtractingj
fromi
and updateans
with the maximum distance found so far. - Set
j
to the current bit positioni
.
- Check if the least significant bit of
-
Right shift the bits of
n
(n >>= 1
) to bring the next bit into the least significant bit position, preparing for the next iteration of the loop. -
Repeat steps 3 and 4 until all 32 bit positions have been checked.
-
Once the loop is finished, the value stored in
ans
is the longest distance between two adjacent1
s in the binary representation ofn
. Returnans
.
In summary, the implementation uses an iteration over the bit positions and bitwise manipulation to identify and measure the distances between the 1
s. The pattern of maintaining a running maximum (ans
) and tracking the last occurrence of interest (j
) is common in problems where successive elements need to be compared or where distances need to be computed.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's say we have the positive integer n = 22
, whose binary representation is 10110
. We want to calculate the longest distance between any two adjacent 1
s in this binary. Now, let's walk through the solution step by step.
-
Initialize
ans
to0
andj
to-1
. -
Iterate from bit position
i = 0
to31
. Forn = 22
, our binary is0000...010110
(in 32-bit form). -
At
i = 0
,n & 1
is0
.n
is right-shifted:n >>= 1
, son
becomes11
. -
At
i = 1
,n & 1
is1
, so we found the first1
. Sincej
is-1
, we just updatej = 1
. -
At
i = 2
,n & 1
is1
again. Now,j
is not-1
, so we calculate the distance:i - j
which is2 - 1 = 1
. We updateans
to1
because1
is larger than the currentans
which is0
. Now setj = 2
. -
At
i = 3
,n & 1
is0
.n
is right-shifted. -
At
i = 4
,n & 1
is0
.n
is right-shifted. -
At
i = 5
,n & 1
is1
. We calculate the distance from the previous1
:i - j
which is5 - 2 = 3
. We updateans
to3
because3
is larger than our currentans
of1
. Now setj = 5
. -
Continue this process until all bits are checked, but since
n
becomes0
after several shifts, the rest of the iterations will not changeans
orj
.
After completing the loop, the value of ans
is 3
. So the longest distance between two adjacent 1
s in the binary representation of 22
is 3
.
Solution Implementation
1class Solution:
2 def binary_gap(self, n: int) -> int:
3 # Initialize maximum distance (gap) and the position of the last found '1'
4 max_gap, last_pos = 0, -1
5
6 # Loop through each bit position
7 for i in range(32):
8 # Check if the least significant bit is '1'
9 if n & 1:
10 # If this is not the first '1' found, calculate the gap
11 if last_pos != -1:
12 gap = i - last_pos
13 max_gap = max(max_gap, gap)
14 # Update the position of the last found '1'
15 last_pos = i
16 # Right shift 'n' to check the next bit
17 n >>= 1
18
19 # Return the maximum distance (gap) between two consecutive '1's in the binary representation
20 return max_gap
21
1class Solution {
2 public int binaryGap(int number) {
3 int maxGap = 0; // Maximum distance found so far
4 // Index to track the rightmost 1 bit we have seen
5 int lastSeenIndex = -1; // -1 indicates that we haven't seen a 1 bit yet
6
7 // Iterate through each bit; 'i' is the position of the current bit, shifting 'number' to the right each time
8 for (int currentPosition = 0; number != 0; currentPosition++, number >>= 1) {
9 // Check if the least significant bit is 1
10 if ((number & 1) == 1) {
11 // If we have seen an earlier 1 bit, update the max gap
12 if (lastSeenIndex != -1) {
13 maxGap = Math.max(maxGap, currentPosition - lastSeenIndex);
14 }
15 // Update the index of the last seen 1 bit
16 lastSeenIndex = currentPosition;
17 }
18 }
19 return maxGap; // Return the maximum distance between two 1 bits in the binary representation
20 }
21}
22
1#include <algorithm> // Include the algorithm library for the max function
2
3class Solution {
4public:
5 int binaryGap(int N) {
6 int maxDistance = 0; // The maximum distance between two consecutive 1's
7 for (int currentPos = 0, lastOnePos = -1;
8 N > 0;
9 ++currentPos, N >>= 1) // Shift N right to process the next bit
10 {
11 if (N & 1) { // Check if the rightmost bit of N is set (is 1)
12 if (lastOnePos != -1) { // There was a previous 1
13 // Update the maximum distance between 1's
14 maxDistance = std::max(maxDistance, currentPos - lastOnePos);
15 }
16 // Update the position of the last 1 encountered
17 lastOnePos = currentPos;
18 }
19 }
20 return maxDistance; // Return the maximum distance found
21 }
22};
23
1function binaryGap(n: number): number {
2 let maxGap = 0; // This will hold the maximum distance between two consecutive 1's.
3 let lastIndex = -1; // This will keep the index of the last 1 bit found.
4
5 // Iterate over the bits of 'n'.
6 // 'i' will serve as the bit position counter.
7 for (let i = 0; n !== 0; i++) {
8 // If the least significant bit is a 1...
9 if (n & 1) {
10 // If it's not the first 1 bit we've found...
11 if (lastIndex !== -1) {
12 // ...update the maxGap with the larger value between the current maxGap and the distance from the last 1 bit.
13 maxGap = Math.max(maxGap, i - lastIndex);
14 }
15 // Update lastIndex to the current bit's position.
16 lastIndex = i;
17 }
18 // Right shift 'n' by 1 bit to process the next bit during the next loop iteration.
19 n >>= 1;
20 }
21 return maxGap; // Return the maximum gap found.
22}
23
Time and Space Complexity
The given code snippet is designed to find the maximum distance between any two consecutive "1" bits in the binary representation of a given integer n
.
Time Complexity:
The time complexity of the code is determined by the number of iterations in the for-loop which is fixed at 32 (since it's considering a 32-bit integer). Therefore, the loop runs a constant number of times, independent of the input size. As a result, the time complexity of the code is O(1)
.
Inside the loop, all operations performed (checking if the least significant bit is 1, updating the maximum distance ans
, shifting of n
, and updating j
) are done in constant time.
Given that the number of operations is fixed and limited by the size of the integer (32 bits in this case), it does not scale with n
, thus confirming that the time complexity is constant.
Space Complexity:
The space complexity of the code is the amount of memory it uses in addition to the input. The code uses a constant amount of extra space for the variables ans
, j
, and i
. These variables are independent of the input size since their size does not grow with n
.
Hence, the space complexity of the code is O(1)
as well, because it allocates a fixed amount of space that does not vary with the size of the input n
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Don’t Miss This!