868. Binary Gap LeetCode Solution

In this guide, you will get 868. Binary Gap LeetCode Solution with the best time and space complexity. The solution to Binary Gap problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Binary Gap solution in C++
Binary Gap solution in Java
Binary Gap solution in Python
Additional Resources

Problem Statement of Binary Gap

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 of 1’s is “10110” with a distance of 2.
The second adjacent pair of 1’s is “10110” with a distance of 1.
The answer is the largest of these two distances, which is 2.
Note that “10110” is not a valid pair since there is a 1 separating the two 1’s underlined.

Example 2:

Input: n = 8
Output: 0
Explanation: 8 in binary is “1000”.
There are not any adjacent pairs of 1’s in the binary representation of 8, so we return 0.

Example 3:

Input: n = 5
Output: 2
Explanation: 5 in binary is “101”.

Constraints:

1 <= n <= 109

Complexity Analysis

Time Complexity: O(\log n)
Space Complexity: O(1)

868. Binary Gap LeetCode Solution in C++

class Solution {
 public:
  int binaryGap(int n) {
    int ans = 0;

    // d := the distance between any two 1s
    for (int d = -32; n; n /= 2, ++d)
      if (n % 2 == 1) {
        ans = max(ans, d);
        d = 0;
      }

    return ans;
  }
};
/* code provided by PROGIEZ */

868. Binary Gap LeetCode Solution in Java

class Solution {
  public int binaryGap(int n) {
    int ans = 0;

    // d := the distance between any two 1s
    for (int d = -32; n > 0; n /= 2, ++d)
      if (n % 2 == 1) {
        ans = Math.max(ans, d);
        d = 0;
      }

    return ans;
  }
}
// code provided by PROGIEZ

868. Binary Gap LeetCode Solution in Python

class Solution:
  def binaryGap(self, n: int) -> int:
    ans = 0
    d = -32  # the distance between any two 1s

    while n:
      if n % 2 == 1:
        ans = max(ans, d)
        d = 0
      n //= 2
      d += 1

    return ans
 # code by PROGIEZ