What is the time complexity of Binary Gap?

The optimal solution has a time complexity of O(log n).

What is the space complexity of Binary Gap?

The space complexity is O(log n).

What data structures are used to solve Binary Gap?

This problem uses Bit Manipulation. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Binary Gap?

Insight 1: Convert the integer to its binary string representation to easily identify '1's and their positions. Insight 2: Iterate through the binary string (or the bits of the integer) to find all occurrences of '1's.

Which companies ask LeetCode 868. Binary Gap in interviews?

This problem is frequently asked at X, eBay.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Binary Gap - LeetCode 868 Solution

Binary Gap - Complete Solution Guide

Binary Gap is LeetCode problem 868, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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. Example 1: Input: n = 22 Output: 2 Explanation: 22 in binary is "10110". The first adjacent pair

Detailed Explanation

The problem requires finding the maximum distance between any two adjacent '1's in the binary representation of a given positive integer 'n'. The distance is defined as the number of '0's (or the number of bits) between the two '1's, plus 1 (or the difference in their indices). If there are fewer than two '1's in the binary representation, the function should return 0.

Solution Approach

The solution iterates through the binary representation of the integer. It maintains the index of the last encountered '1'. When it finds a '1', it calculates the distance from the current '1' to the last '1', and updates the maximum distance found so far. The distance is calculated as the difference between the current index and the index of the last '1'. After processing all bits, the maximum distance is returned.

Step-by-Step Algorithm

Step 1: Convert the integer 'n' to its binary string representation (or directly process bits without explicit conversion).
Step 2: Initialize variables: 'max_distance' to 0 (to store the maximum distance found so far), and 'last_one' to -1 (to indicate that no '1' has been found yet).
Step 3: Iterate through the binary string (or bits of the integer).
Step 4: In each iteration, check if the current bit is '1'.
Step 5: If the current bit is '1', and 'last_one' is not -1 (meaning a previous '1' was found), calculate the distance between the current '1' and the previous '1' (distance = current_index - last_one).
Step 6: Update 'max_distance' with the maximum of 'max_distance' and the calculated 'distance'.
Step 7: Update 'last_one' to the current index.
Step 8: After iterating through all the bits, return 'max_distance'.

Key Insights

Insight 1: Convert the integer to its binary string representation to easily identify '1's and their positions.
Insight 2: Iterate through the binary string (or the bits of the integer) to find all occurrences of '1's.
Insight 3: Keep track of the index of the last '1' encountered and compute the distance to the current '1'.

Complexity Analysis

Time Complexity: O(log n)

Space Complexity: O(log n)

Topics

This problem involves: Bit Manipulation.

Companies

Asked at: X, eBay.

Binary Gap | LeetCode 868

Easy

Bit Manipulation

Time: O(log n)Space: O(log n)

Solution Code

Available in:

class Solution {
    public int binaryGap(int n) {
        String binary = Integer.toBinaryString(n);
        int maxGap = 0;
        int lastOne = -1;
        for (int i = 0; i < binary.length(); i++) {
            if (binary.charAt(i) == '1') {
                if (lastOne != -1) {
                    maxGap = Math.max(maxGap, i - lastOne);
                }
                lastOne = i;
            }
        }
        return maxGap;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 868: Binary Gap - Detailed explanation and solution approaches.

Topics

Bit Manipulation

Companies

XeBay

Stats

Difficulty:Easy

Languages:4

Companies:2

Problem #:868

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

8 steps

1
Step 1: Convert the integer 'n' to its binary string representation (or directly process bits without explicit conversion).
2
Step 2: Initialize variables: 'max_distance' to 0 (to store the maximum distance found so far), and 'last_one' to -1 (to indicate that no '1' has been found yet).
3
Step 3: Iterate through the binary string (or bits of the integer).
4
Step 4: In each iteration, check if the current bit is '1'.
5
Step 5: If the current bit is '1', and 'last_one' is not -1 (meaning a previous '1' was found), calculate the distance between the current '1' and the previous '1' (distance = current_index - last_one).
6
Step 6: Update 'max_distance' with the maximum of 'max_distance' and the calculated 'distance'.
7
Step 7: Update 'last_one' to the current index.
8
Step 8: After iterating through all the bits, return 'max_distance'.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(log n)

🚀 Logarithmic - Very efficient! Halves the problem each step.

💾

Space Complexity

O(log n)

🎯 Logarithmic space - Very memory efficient!

📝

Why?

The time complexity is O(log n) because the number of bits in the binary representation of 'n' is log base 2 of 'n'. We iterate through all the bits, so the time complexity is directly proportional to the number of bits. The space complexity is O(1) because we only use a few variables to store the maximum distance, the index of the last '1', and the current index, regardless of the input 'n'.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Precompute Binary String and Iterate

Similar to the Python solution, first convert the integer to its binary string representation, store the indices of all '1's in a list, and then iterate through the list to calculate the maximum distance between adjacent indices.

Time: O(log n)Space: O(log n)

Trade-offs: Uses more space (O(log n)) to store the indices, but may be more readable for some. The space complexity makes it less efficient than the main solution.

✨

Key Insights

1Insight 1: Convert the integer to its binary string representation to easily identify '1's and their positions.
2Insight 2: Iterate through the binary string (or the bits of the integer) to find all occurrences of '1's.
3Insight 3: Keep track of the index of the last '1' encountered and compute the distance to the current '1'.

📚

Key Terms Explained

For Students

Edge Cases

Edge case 1: n = 1 (binary is '1'). Only one '1', so the result is 0. The algorithm correctly handles this because lastOne remains -1 and the condition to calculate maxGap is never true.
Edge case 2: n = 8 (binary is '1000'). Only one '1', so the result is 0. Similar to edge case 1, the algorithm handles this correctly.
Edge case 3: n = 3 (binary is '11'). Two adjacent '1's, distance is 1. The algorithm correctly calculates the distance as 1.
Edge case 4: n with no adjacent 1s. The algorithm will correctly compute the maximum gap if there are non-adjacent 1s.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the case where there are fewer than two '1's in the binary representation. The code must return 0 in this case.

✗Common mistake 2: Incorrectly calculating the distance between '1's. The distance is the difference between their indices.

✗Common mistake 3: Off-by-one errors when calculating the distance.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Error correction codes in digital communication. Binary gaps can be related to the burst error correcting capability of a code.

🏦Real-world scenario 2: Analyzing binary data in hardware or software systems. Detecting patterns of '1's and '0's is a common task.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

XOR is your friend for "find the single number" problems. Remember: n & (n-1) clears the lowest set bit.

🎯 Interview Tip

Use this problem to demonstrate clean code practices. Variable naming and code organization matter.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 27, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 14

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 7

❓

Frequently Asked Questions

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Binary Gap"?

For this easy-level Bit Manipulation problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether standard techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?