survival8: Discussion on "Binary Gap - A problem of iterations"

To See All Articles About Technology: Index of Lessons in Technology

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:

python
def solution(N):
        binary_str = bin(N)[2:]  # Convert N to binary and remove the '0b' prefix
        max_gap = 0
        current_gap = 0
        counting = False
    
        for char in binary_str:
            if char == '1':
                if counting:
                    max_gap = max(max_gap, current_gap)
                current_gap = 0
                counting = True
            elif counting:
                current_gap += 1
    
        return max_gap

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 updates max_gap if 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:

python
print(solution(9))      # Output: 2
    print(solution(529))    # Output: 4
    print(solution(20))     # Output: 1
    print(solution(15))     # Output: 0
    print(solution(32))     # Output: 0

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() and i.group() call → O(1).
- i.group().count('0') → in worst case O(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 to log N matches.

✅ Space Complexity

n is 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?

How is your code a Greedy algorithm?

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:

python
def solution(N):
        binary_str = bin(N)[2:]
        max_gap = 0
        current_gap = 0
        counting = False
    
        for char in binary_str:
            if char == '1':
                if counting:
                    max_gap = max(max_gap, current_gap)  # ← local decision
                current_gap = 0
                counting = True
            elif counting:
                current_gap += 1

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_gap as 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?

survival8

Friday, April 25, 2025

Discussion on "Binary Gap - A problem of iterations"