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;
}
}
Input
Output
#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;
};
Input
Output
#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
Input
#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;
}
}
}
Input