Question

868. Binary Gap

中文文档

Description

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

Solutions

Solution 1

class Solution:
  def binaryGap(self, n: int) -> int:
    ans, j = 0, -1
    for i in range(32):
      if n & 1:
        if j != -1:
          ans = max(ans, i - j)
        j = i
      n >>= 1
    return ans

class Solution {
  public int binaryGap(int n) {
    int ans = 0;
    for (int i = 0, j = -1; n != 0; ++i, n >>= 1) {
      if ((n & 1) == 1) {
        if (j != -1) {
          ans = Math.max(ans, i - j);
        }
        j = i;
      }
    }
    return ans;
  }
}

class Solution {
public:
  int binaryGap(int n) {
    int ans = 0;
    for (int i = 0, j = -1; n; ++i, n >>= 1) {
      if (n & 1) {
        if (j != -1) ans = max(ans, i - j);
        j = i;
      }
    }
    return ans;
  }
};

func binaryGap(n int) int {
  ans := 0
  for i, j := 0, -1; n != 0; i, n = i+1, n>>1 {
    if (n & 1) == 1 {
      if j != -1 && ans < i-j {
        ans = i - j
      }
      j = i
    }
  }
  return ans
}

function binaryGap(n: number): number {
  let res = 0;
  let j = -1;
  for (let i = 0; n !== 0; i++) {
    if (n & 1) {
      if (j !== -1) {
        res = Math.max(res, i - j);
      }
      j = i;
    }
    n >>= 1;
  }
  return res;
}

impl Solution {
  pub fn binary_gap(mut n: i32) -> i32 {
    let mut res = 0;
    let mut i = 0;
    let mut j = -1;
    while n != 0 {
      if (n & 1) == 1 {
        if j != -1 {
          res = res.max(i - j);
        }
        j = i;
      }
      n >>= 1;
      i += 1;
    }
    res
  }
}