Counting the number of consecutive 1's in binary hackerrank.com Task:


  Given a base-10 integer, n, convert it to binary (base-2). Then find and print the base-10 integer denoting the maximum number of consecutive 1's in n's binary representation.


This question has already been answered but it was in Ruby and I couldn't quite understand the concept, I am just starting to code. What can you suggest me to improve on this piece of code? I think its quite long considering the work it does or is this the efficient solution?

count = 0
max_value = 1

if __name__ == '__main__':
    n = int(input())
    binary_num = bin(n).split("b")
    binary_num = binary_num[1]
    print(binary_num)
    for index, i in enumerate(binary_num):
        if i == "1":
            count += 1
            next_item = index + 1 
            while next_item &lt; len(binary_num):           
                if binary_num[next_item] == "1":
                    count += 1
                    counter = count
                    temp = counter                    
                    next_item += 1
                    if temp &gt; max_value:
                        max_value = temp
                else:
                    counter = count                 
                    count = 0 
                    break
        if next_item == (len(binary_num)):
            break

    print("count is =",max_value)
I think its quite long considering the work it does


Your instinct is right - it's quite long. It can be implemented with much fewer lines of code, especially in Python. A solution from @RomanPerekhrest highlights it quite well.


  is this the efficient solution?


From the time complexity prospective, it's not an efficient solution. It's O(n2), where n - number of binary digits in your number. Why? Because in your outer loop, you process each digit one by one regardless of the results in your inner loop. So, if your inner loop finds a segment of ones you don't move ì and index to a bit position following this segment. Instead, you pick a second bit in this segment and find the same segment without the first bit again.

For instance, let's say we have a number which binary representation is 111110. Then your algorithm will find the following segments of ones:

11111  | 4 inner loop steps
 1111  | 3 inner loop steps
  111  | 2 inner loop steps
   11  | 1 inner loop steps
    1  | 0 inner loop steps


An optimal solution has a O(n) time complexity. I'll leave it up to you to update your code based on the explanation above. 

Bonus

I noticed that each answer uses bin() to calculate the longest segment of ones. However, it's not really needed since this approach has an additional O(n) space complexity (as you recall it from the previous paragraph, n - number of binary digits). 

We could just use bitwise operators to achieve the same result. For example, let's say there's a number 1100011101. It has 3 separate segments of ones: Now, let's play a bit - we will calculate a left shifted version of x and then perform bitwise AND on it. Then, for the shifted version we will calculate its left shifted number and so on.

1 1 0 0 0 1 1 1 0 1 0  (x)
         &amp;
1 0 0 0 1 1 1 0 1 0 0  (x &lt;&lt; 1)
---------------------
1 0 0 0 0 1 1 0 0 0 0  y = ((x) &amp; (x &lt;&lt; 1))


1 0 0 0 0 1 1 0 0 0 0  (y)
         &amp; 
0 0 0 0 1 1 0 0 0 0 0  (y &lt;&lt; 1)
---------------------
0 0 0 0 0 1 0 0 0 0 0  z = ((y) &amp; (y &lt;&lt; 1))


0 0 0 0 0 1 0 0 0 0 0  (z)
         &amp; 
0 0 0 0 1 0 0 0 0 0 0  (z &lt;&lt; 1)
---------------------
0 0 0 0 0 0 0 0 0 0 0  ((z) &amp; (z &lt;&lt; 1))


So, as you can see it took us 3 steps to reach 0. But 3 is also the length of the longest segment of ones. And it's not a coincidence because bitwise AND of a number and its shifted version shortens each segment of ones by 1. Hence, the longest segment will lose all its ones after &lt; length of the longest segment of ones > steps.

Code

def find_max_ones(number):
    maxLength = 0

    while number &gt; 0:
        left_shifted_number = number &lt;&lt; 1
        number = number &amp; left_shifted_number
        maxLength += 1

    return maxLength


if __name__ == '__main__':
    number = int(input('Enter integer number:'))
    max_ones = find_max_ones(number)

    print("Length of the longest segment is ", str(max_ones))