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
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;
};
Copy The Code &
Try With Live Editor
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
Copy The Code &
Try With Live Editor
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;
}
}
}
Copy The Code &
Try With Live Editor
Input