LeetCode 868 - Binary Gap

https://leetcode.com/problems/binary-gap/

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.

distance between '1' and '1'
let`s check all distances in binary representation
10010001101
1. first distance 1001 (from 0 to 3 index) -> distance 3
2.10001 (from 3 to 7) -> distance 4
3.11 (from 7 to 8) -> distance 1
4.101 (from 8 to 10) -> distance 2

Since we wanted to inspect the distance between consecutive 1s in the binary representation of N, let's write down the index of each 1 in that binary representation. For example, if N = 22 = 0b10110, then we'll write A = [1, 2, 4]. This makes it easier to proceed, as now we have a problem about adjacent values in an array.

Algorithm

Let's make a list A of indices i such that N has the ith bit set.

With this array A, finding the maximum distance between consecutive 1s is much easier: it's the maximum distance between adjacent values of this array.

• Time Complexity: $O(\log N)$. Note that $\log N$ is the number of digits in the binary representation of $N$.
• Space Complexity: $O(\log N)$, the space used by A.

  public int binaryGap(int N) {

    int[] A = new int[32];

    int t = 0;

    for (int i = 0; i < 32; ++i)

      if (((N >> i) & 1) != 0)

        A[t++] = i;

    int ans = 0;

    for (int i = 0; i < t - 1; ++i)

      ans = Math.max(ans, A[i + 1] - A[i]);

    return ans;

  }

In Approach 1, we created an array A of indices i for which N had the ith bit set.

Since we only care about consecutive values of this array A, we don't need to store the whole array. We only need to remember the last value seen.

Algorithm

We'll store last, the last value added to the virtual array A. If N has the ith bit set, a candidate answer is i - last, and then the new last value added to A would be last = i.

• Time Complexity: $O(\log N)$. Note that $\log N$ is the number of digits in the binary representation of $N$.

  public int binaryGap(int N) {

    int last = -1, ans = 0;

    for (int i = 0; i < 32; ++i)

      if (((N >> i) & 1) > 0) {

        if (last >= 0)

          ans = Math.max(ans, i - last);

        last = i;

      }

    return ans;

  }

https://leetcode.com/problems/binary-gap/discuss/149835/C%2B%2BJavaPython-Dividing-by-2

One pass on N in binary from right to left.
d means the distance from the last 1 position.
d is initial to a small enough value -32

    public int binaryGap(int N) {
        int res = 0;
        for (int d = -32; N > 0; N /= 2, d++)
            if (N % 2 == 1) {
                res = Math.max(res, d);
                d = 0;
            }
        return res;
    }

public int binaryGap(int n) { int maxD = 0; int d = 0; int bitCount = 0; int lastBit = 0; while(n>0){ bitCount++; int t = n&1; if(t==1){ d = lastBit !=0 ? bitCount-lastBit : 0; maxD = Math.max(maxD, d); lastBit = bitCount; } n = n>>1; } return maxD; }

public int binaryGap(int N) { String binary = Integer.toBinaryString(N); int dist = 0; int lastIndex = -1; for (int i = 0; i < binary.length(); i++) { if(binary.charAt(i) == '1') { if (lastIndex == -1) { lastIndex = i; continue; } if(i - lastIndex >= dist) { dist = i - lastIndex; } lastIndex = i; } } return dist; }