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 no two consecutive 1’s, return 0.

Clarifying Questions

Before diving into the solution, let’s clarify a few points:

  1. Input Constraints: What is the range of the input integer n?
    • Answer: 1 <= n <= 10^9
  2. Output Type: What is the output type?
    • Answer: The output is an integer representing the longest distance.

Strategy

Here’s a step-by-step approach to solve this problem:

  1. Convert to Binary: Convert the integer n into its binary form.
  2. Identify Positions: Traverse the binary string and record the positions of all ‘1’s.
  3. Compute Gaps: Calculate the distances between consecutive positions of ‘1’.
  4. Find Maximum Gap: Return the maximum distance found.

Code

Below is the Java code that implements the above strategy:

public class Solution {
    public int binaryGap(int n) {
        String binaryString = Integer.toBinaryString(n);
        int lastPos = -1;
        int maxDistance = 0;
        
        for (int i = 0; i < binaryString.length(); i++) {
            if (binaryString.charAt(i) == '1') {
                if (lastPos != -1) {
                    maxDistance = Math.max(maxDistance, i - lastPos);
                }
                lastPos = i;
            }
        }
        
        return maxDistance;
    }
    
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.binaryGap(22)); // Output: 2
        System.out.println(solution.binaryGap(5));  // Output: 2
        System.out.println(solution.binaryGap(6));  // Output: 1
        System.out.println(solution.binaryGap(8));  // Output: 0
    }
}

Time Complexity

Explanation

  1. The Integer.toBinaryString(n) method converts the integer n to its binary representation.
  2. We then iterate through the binary string to find positions where the character is ‘1’.
  3. We calculate the distance between the current position of ‘1’ and the last position of ‘1’, updating the maximum distance found.
  4. If no two consecutive ‘1’s are found, the program will correctly return 0.

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