Solution


Approach 1: Store Indexes

Intuition

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.

Complexity Analysis

  • Time Complexity: . Note that is the number of digits in the binary representation of .

  • Space Complexity: , the space used by A.


Approach 2: One Pass

Intuition

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.

Complexity Analysis

  • Time Complexity: . Note that is the number of digits in the binary representation of .

  • Space Complexity: .


Analysis written by: @awice.