Teaching Kids Programming – Longest Consecutive Run of 1s in Binary

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a non-negative integer n, return the length of the longest consecutive run of 1s in its binary representation.

Constraints
0 ≤ n < 2 ** 31
Example 1
Input
n = 156
Output
3
Explanation
156 is10011100 in binary and there’s a run of length 3.

Consecutive Ones by Split and Count

We can use the bin function in Python to convert integer to binary string and we have to strip the first two characters ‘0b’. Then, we split the binary string by ‘0’ which then we can count the lengths for each group of ones (consecutive ones).

1
2
3
4

class Solution:
    def consecutiveOnes(self, n):
        # return max(len(x) for x in bin(n)[2:].split('0'))
        return max(map(len, bin(n)[2:].split('0')))

class Solution:
    def consecutiveOnes(self, n):
        # return max(len(x) for x in bin(n)[2:].split('0'))
        return max(map(len, bin(n)[2:].split('0')))

The time complexity is O(LogN).

Count Bit by Bit – Consecutive Ones

We can check each bit one by one – having a counter for consecutive ones and reset when we meet zeros.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def consecutiveOnes(self, n):
        ans = 0
        c = 0
        while n:
            if n & 1:
                c += 1
            else:
                c = 0
            ans = max(ans, c)
            n >>= 1
        return ans

class Solution:
    def consecutiveOnes(self, n):
        ans = 0
        c = 0
        while n:
            if n & 1:
                c += 1
            else:
                c = 0
            ans = max(ans, c)
            n >>= 1
        return ans

The time complexity is O(LogN). The space complexity is O(1).

–EOF (The Ultimate Computing & Technology Blog) —