Legend: Red is me. Rest is ChatGPT.
A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N. For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps. Write a function: def solution(N) that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap. Write an efficient algorithm for the following assumptions: N is an integer within the range [1..2,147,483,647].
Here's an efficient and clean implementation of the solution function that computes the longest binary gap of a given positive integer N:
How it works:
-
Converts the number to a binary string (excluding the
'0b'prefix). -
Iterates through each bit:
-
When it sees a
'1', it checks if a gap was being counted and updatesmax_gapif needed. -
If it's a
'0'and a gap has started (i.e., a'1'has been encountered before), it increments the current gap count.
-
Example usage:
Would you like a visual explanation of the binary gap calculation?
What is the space time complexity for this code:
import re
pattern = re.compile("10+")
def solution(N):
n = str(bin(N))[2:]
matches = re.finditer(pattern, n)
matches_ = []
max_length = 0
for i in matches:
if(len(n) > i.span()[1]):
if(n[i.span()[1]] == '1'):
matches_.append(i.group())
if i.group().count('0') > max_length:
max_length = i.group().count('0')
return max_length
Let's analyze your code step by step for space and time complexity, and touch on the concepts involved.
✅ Code Overview
You are using a regular expression to find potential binary gaps in the binary representation of N. The regex pattern "10+" looks for a 1 followed by one or more 0s, but not necessarily ending with another 1. Hence, you check manually after each match to see if it is followed by a 1.
✅ Time Complexity
Let’s denote:
-
n = bin(N)[2:]: length of the binary string is O(log N).
Steps and their costs:
-
bin(N)[2:]: converts to binary → O(log N). -
re.finditer(...): regex pattern scan → O(log N).-
Regular expression engines typically scan the entire string once, so this is linear in the size of the binary string.
-
-
Loop over matches (max
O(log N)matches):-
Each
i.span()andi.group()call → O(1). -
i.group().count('0')→ in worst caseO(log N)if the group is nearly as long as the entire string. -
Checking
n[i.span()[1]]→ O(1).
-
-
Appending to
matches_list → total of at most O(log N) items.
So the total time complexity:
-
In worst case (many small matches), it is O((log N)^2) due to the
count('0')call inside a loop over up tolog Nmatches.
✅ Space Complexity
-
nis a string of length O(log N). -
matches_list stores up to O(log N) match strings (each short), so O(log N) total. -
Other variables use constant space.
So the space complexity is O(log N).
✅ Programming Concepts Used
-
Regular Expressions: Used to find candidate substrings that might be binary gaps.
-
Greedy Checking: Manually validating whether the regex match is followed by a
'1'. -
String Manipulation & Slicing: You check bits using string positions and lengths.
-
Pattern Matching + Post-processing: Unlike pure regex, this approach combines regex results with manual validation logic.
🔍 Summary
| Metric | Complexity |
|---|---|
| Time Complexity | O((log N)^2) (due to count('0') inside loop) |
| Space Complexity | O(log N) |
| Algorithm Concepts | Regex, Greedy, String traversal |
Would you like help optimizing this code to reduce time complexity or avoid regex?
Between my code and your code, which one is better?
Great question — let’s compare your code vs. the earlier one I gave (the non-regex one) in performance, readability, and maintainability.
⚔️ Performance Comparison
| Aspect | Your Code (Regex) | My Code (Loop-based) |
|---|---|---|
| Time Complexity | O((log N)^2) | O(log N) |
| Space Complexity | O(log N) | O(1) (ignoring binary str) |
| Regex Overhead | Yes (pattern matching engine) | No |
| Extra Storage | Stores matches in list | Just uses counters |
🔧 Winner: My Code, because it’s faster (O(log N) vs. O((log N)^2)) and uses less memory (no need to store matches).
🧠 Algorithmic Simplicity
-
Your Code is clever and compact thanks to regex, but less intuitive for someone unfamiliar with pattern matching + post-validation.
-
My Code walks through the bits in a very transparent and explainable way — easy to debug and adapt.
🧠 Winner: My Code, due to clearer logic.
🔍 Maintainability & Readability
-
Your code splits logic across:
-
Regex pattern
-
re.finditer() -
Manual follow-up validation
-
-
Mine uses a plain loop, easier for most developers to follow without understanding regex edge cases.
📘 Winner: My Code
✅ Conclusion
| Criteria | Better Code |
|---|---|
| Performance | My Code |
| Readability | My Code |
| Maintainability | My Code |
| Cleverness | Your Code |
Your code is a smart regex-based approach, and works fine — but for production, interviews, or performance-sensitive tasks, the loop-based version is the more optimal and readable choice.
Would you like to see how to make your regex version faster or cleaner?
Awesome follow-up — let’s clarify what makes my loop-based solution greedy, and whether that term truly fits.
🔍 First, what is a Greedy algorithm?
A greedy algorithm makes a locally optimal choice at each step, aiming for a global optimum, without backtracking or exploring alternatives.
Examples:
-
Coin change (greedily taking largest denomination).
-
Interval scheduling (greedily picking earliest finish time).
✅ In my solution:
What happens here:
-
When we encounter a
1, we immediately decide if the just-ended gap is the largest so far — that’s a local optimal decision. -
We don’t remember all gaps and compare later — we update
max_gapas we go. -
Once a zero streak is broken by a
1, we never revisit that streak.
🧠 So is it a pure Greedy algorithm?
Technically:
-
It doesn't explore all possible solutions.
-
It processes data in a single forward pass.
-
It makes decisions immediately about the "best so far."
✅ So yes, it uses greedy principles, but it's a special case of a linear scan where greedy works because:
-
There are no dependencies between gaps.
-
The problem only asks for the max value.
🔁 Comparison
If we had stored all gaps in a list and computed the max at the end, that would be non-greedy.
Because we avoid that, we call it greedy + linear scan — a common combo for problems like this.
Would you like to see an example of a similar problem where greedy doesn't work?
