Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/868.html

868. Binary Gap (Easy)

Given a positive integer N, find and return the longest distance between two consecutive 1's in the binary representation of N.

If there aren't two consecutive 1's, return 0.

 

Example 1:

Input: 22
Output: 2
Explanation: 
22 in binary is 0b10110.
In the binary representation of 22, there are three ones, and two consecutive pairs of 1's.
The first consecutive pair of 1's have distance 2.
The second consecutive pair of 1's have distance 1.
The answer is the largest of these two distances, which is 2.

Example 2:

Input: 5
Output: 2
Explanation: 
5 in binary is 0b101.

Example 3:

Input: 6
Output: 1
Explanation: 
6 in binary is 0b110.

Example 4:

Input: 8
Output: 0
Explanation: 
8 in binary is 0b1000.
There aren't any consecutive pairs of 1's in the binary representation of 8, so we return 0.

 

Note:

  • 1 <= N <= 10^9

Companies:
Twitter, eBay

Related Topics:
Math

Solution 1.

// OJ: https://leetcode.com/problems/binary-gap/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int binaryGap(int N) {
        int prev = -1, i = 0, ans = 0;
        while (N) {
            if (N % 2) {
                if (prev != -1) ans = max(ans, i - prev);
                prev = i;
            }
            N /= 2;
            ++i;
        }
        return ans;
    }
};

  • class Solution {
    public int binaryGap(int N) {
        if (N <= 2)
            return 0;
        List<Integer> list = new ArrayList<Integer>();
        int position = 0;
        while (N > 0) {
            int curDigit = N & 1;
            if (curDigit == 1)
                list.add(position);
            N >>>= 1;
            position++;
        }
        int size = list.size();
        if (size <= 1)
            return 0;
        int max = 0;
        for (int i = 1; i < size; i++) {
            int prev = list.get(i - 1), cur = list.get(i);
            max = Math.max(max, cur - prev);
        }
        return max;
    }
}

############

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;
    }
}

  • // OJ: https://leetcode.com/problems/binary-gap/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int binaryGap(int N) {
        int prev = -1, i = 0, ans = 0;
        while (N) {
            if (N % 2) {
                if (prev != -1) ans = max(ans, i - prev);
                prev = i;
            }
            N /= 2;
            ++i;
        }
        return ans;
    }
};

  • 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(object):
    def binaryGap(self, N):
        """
        :type N: int
        :rtype: int
        """
        binary = bin(N)[2:]
        dists = [0] * len(binary)
        left = 0
        for i, b in enumerate(binary):
            if b == '1':
                dists[i] = i - left
                left = i
        return max(dists)

  • 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
    }
}

All Problems

All Solutions