Algorithm


Problem Name: 868. Binary Gap

Problem Link: https://leetcode.com/problems/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

 

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class Solution {
    public int binaryGap(int n) {
        int lastOnePosition = -1;
        int currPosition = 0;
        int maxGap = 0;
        while (n > 0) {
            int rem = n % 2;
            n /= 2;
            if (rem == 1) {
                if (lastOnePosition != -1) {
                    maxGap = Math.max(maxGap, currPosition - lastOnePosition);
                }
                lastOnePosition = currPosition;
            }
            currPosition++;
        }
        return maxGap;
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
n = 22

Output

x
+
cmd
2

#2 Code Example with Javascript Programming

Code - Javascript Programming


const binaryGap = function(N) {
  const bin = (N >>> 0).toString(2);
  const idxArr = [];
  for (let i = 0; i  <  bin.length; i++) {
    const num = bin.charAt(i);
    if (num === "1") {
      idxArr.push(i);
    }
  }
  let maxConLen = 0;
  for (let idx = 0; idx  <  idxArr.length - 1; idx++) {
    if (idxArr[idx + 1] - idxArr[idx] > maxConLen) {
      maxConLen = idxArr[idx + 1] - idxArr[idx];
    }
  }

  return maxConLen;
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
n = 22

Output

x
+
cmd
2

#3 Code Example with Python Programming

Code - Python Programming


class Solution:
    def binaryGap(self, N):
        pre = dist = 0
        for i, c in enumerate(bin(N)[2:]):
            if c == "1":
                dist = max(dist, i - pre)
                pre = i
        return dist
Copy The Code & Try With Live Editor

Input

x
+
cmd
n = 8

#4 Code Example with C# Programming

Code - C# Programming


using System;

namespace LeetCode
{
    public class _0868_BinaryGap
    {
        public int BinaryGap(int N)
        {
            var last = -1;
            var result = 0;
            for (int i = 0; i  <  32; i++)
            {
                if (((N >> i) & 1) == 1)
                {
                    if (last >= 0)
                        result = Math.Max(result, i - last);
                    last = i;
                }
            }

            return result;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
n = 8
Advertisements

Demonstration


Previous
#867 Leetcode Transpose Matrix Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#869 Leetcode Reordered Power of 2 Solution in C, C++, Java, JavaScript, Python, C# Leetcode