algoadvance

Leetcode 868. Binary Gap

Problem Statement

Given a positive integer n, find and return the longest distance between any two consecutive 1’s in the binary representation of n. If there are less than two 1’s, return 0.

Clarifying Questions

  1. Input Range:
    • What is the range of the integer n?

    Answer: n is a positive integer which means 1 ≤ n ≤ 10^9.

  2. Binary Representation:
    • Should we handle the binary conversion manually or can we use built-in functions?

    Answer: Using built-in functions for binary conversion is acceptable as it simplifies the problem.

Strategy

  1. Convert the integer n to its binary representation.
  2. Traverse the binary string and record the positions of each ‘1’.
  3. Compute the distances between each pair of consecutive ‘1’s.
  4. Return the maximum distance found or return 0 if there are fewer than two ‘1’s.

Code

#include <iostream>
#include <vector>
#include <bitset>

class Solution {
public:
    int binaryGap(int n) {
        // Convert the number to its binary representation
        std::string binary = std::bitset<32>(n).to_string();

        // Initialize the variables
        int max_gap = 0;
        int last_position = -1;
        
        for (int i = 0; i < binary.size(); ++i) {
            if (binary[i] == '1') {
                if (last_position != -1) {
                    max_gap = std::max(max_gap, i - last_position);
                }
                last_position = i;
            }
        }
        
        return max_gap;
    }
};

int main() {
    Solution solution;
    int n = 22;  // Example input
    std::cout << "Binary Gap: " << solution.binaryGap(n) << std::endl;
    return 0;
}

Explanation:

  1. Binary Conversion: std::bitset<32>(n).to_string() converts the integer n to its binary representation in a string format.
  2. Max Gap Calculation: Iterate through the binary string:
    • For each ‘1’, calculate the distance from the last recorded ‘1’.
    • Update the maximum gap if the current gap is larger.
    • Update the last position of ‘1’.

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI