Counting the number of consecutive 1's in binary

Question

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 < len(binary_num):           
                if binary_num[next_item] == "1":
                    count += 1
                    counter = count
                    temp = counter                    
                    next_item += 1
                    if temp > max_value:
                        max_value = temp
                else:
                    counter = count                 
                    count = 0 
                    break
        if next_item == (len(binary_num)):
            break

    print("count is =",max_value)

Answer 1

The whole idea is achievable with a few lines of code and based on designating segments of 1 's items (repeated consecutive sequence) using 0 segments as separators.
See the concise solution below:

def find_max_ones(num):
    if not num:
        return 0
    bin_num = bin(num)[2:]
    print(bin_num)
    return len(max(bin_num.replace('0', ' ').split(), key=len))


if __name__ == '__main__':
    num = int(input('Enter integer number:'))
    max_ones = find_max_ones(num)
    print("max 1's count is", max_ones)

Sample usage:

Enter integer number:1000
1111101000
max 1's count is 5

Answer 2

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(n²), 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)
         &
1 0 0 0 1 1 1 0 1 0 0  (x << 1)
---------------------
1 0 0 0 0 1 1 0 0 0 0  y = ((x) & (x << 1))


1 0 0 0 0 1 1 0 0 0 0  (y)
         & 
0 0 0 0 1 1 0 0 0 0 0  (y << 1)
---------------------
0 0 0 0 0 1 0 0 0 0 0  z = ((y) & (y << 1))


0 0 0 0 0 1 0 0 0 0 0  (z)
         & 
0 0 0 0 1 0 0 0 0 0 0  (z << 1)
---------------------
0 0 0 0 0 0 0 0 0 0 0  ((z) & (z << 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 < length of the longest segment of ones > steps.

Code

def find_max_ones(number):
    maxLength = 0

    while number > 0:
        left_shifted_number = number << 1
        number = number & 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))

Answer 3

This is a good opportunity to learn two things, separation of concerns and the standard library module itertools.

You have three separate issues, each of which you can put into their own function:

1. Take input from the user
2. Turn it into a sequence of 0 and 1.
3. Find the longest run of 1.

For the user input it can be as simple as your one line, or slightly more sophisticated as this function:

def ask_user(message="", type_=str):
    while True:
        try:
            return type_(input(message))
        except ValueError:
            print("wrong type, try again")

Later you might want to add things like validator functions, allowed ranges, etc, but this should suffice for now.

Turning the number into a binary sequence is easy:

def to_binary(n):
    return bin(n)[2:]

Or even like this, as mentioned in the comments by Eric:

def to_binary(x):
    return format(x, "b")

And for the last step you can use itertools.groupby:

from itertools import groupby

def longest_run_of(it, value):
    return max(len(list(group))
               for c, group in groupby(it)
               if c == value)

Putting it all together, using some f-string for slightly easier string formatting:

if __name__ == "__main__":
    n = ask_user("Enter a number: ", int)
    n_bin = to_binary(n)
    longest_run = longest_run_of(n_bin, "1")
    print(f"count is = {longest_run}")

Once you are this far it becomes a lot easier to try and test different implementations, as you can change (and test) each part individually. At this point it might make sense to start profiling to see which implementation is the fastest, depending on your needs.

Answer 4

I am a newbie to coding myself, but your logic is kind of hard to follow - probably my problem. You should use slicing operation on the string to get the '0b' removed from bin() function result as i feel like a cleaner method.

Here's an alternate logic I came up with

count = 0
final_count = 0
concecutive_check = False

if __name__ == '__main__':
    n = int(input())
    bin_representation = bin(n)[2:] #slice operation to remove 'ob'
    print(bin_representation)

    for num in bin_representation:
        if concecutive_check and num == '1':
            count +=1
        elif concecutive_check and num == '0':
            concecutive_check = False
            if count > final_count:
                final_count = count
            count = 0
        elif num == '1':
            concecutive_check = True
            count = 1

    if count > final_count: # final check just in case the binary string ends in 1 and doesn't trigger the above if statements
        final_count = count
    print(f'{final_count} max sequence count')

As general coding practices, comments where appropriate would be good (as in if something is understandable from the name of the function or object it doesn't need a comment), or if there is a nonsensical aspect like my second count > final count check, explaining the reason for that.

Another thing i noticed is you using the enumerate operation without really using the index for anything beyond as a counter for loop... why? wouldn't the generic for loop over iterable take care of that?

I think the logic route you used is a bit round about way of doing it, a single boolean state variable and two int variable is all you need to keep track of the longest count over the string.

Answer 5

A few improvements following principles of Cleancode and Divide & Conquer:

1. Split into small tasks, each one a function.
2. Use meaningful names.
3. Leverage the language's power.

Split into small tasks, each one a function

The challenge's description explicitly names 2 tasks, thus implemented in functions:

1. convert_to_binary(number)
2. max_consecutive_1s_of_binary(binary)

Above functions already have meaningful names (see 2), expressing what they do.

Besides you have other tasks, given implicitly:

1. Read a (decimal) number from STDIN
2. Determine length of a sequence (of max consecutive 1s)
3. Print number to STDOUT (length of max consecutive 1s)

These side-tasks can be implemented using existing functions (in Python).

Use meaningful names

From above functional design you can derive data-structures and variables. Name them to express what (in context of your program) they contain:

1. number_input
2. binary_representation
3. max_consecutive_1s
4. length_of_max_consecutive_1s

Leverage the language's power

Use already built-in functions where suitable:

1. Use bin and slicing for stripping of the binary marker; or use format(number, 'b') directly
2. string-splitting by regex for split the binary representation into consecutive 1s using 0 as split-marker (very smart solution by Roman)
3. max for finding the maximum of a list based on some key criterion (here the length)

See also

• https://stackoverflow.com/questions/37605328/calculating-consecutive-1s-in-a-binary-number
• https://www.geeksforgeeks.org/maximum-consecutive-ones-or-zeros-in-a-binary-array/

Answer 6

I don't know about the other programming languages but it's quite easy to implement this particular program using inbuilt functions. So here is my code:

from itertools import groupby  
def output(n):  
    binary_num = bin(n).replace("0b","")  
    print(max(len(list(group)) for i,group in groupby(binary_num) if i== '1'))  


if __name__ == '__main__':  
    n = int(input())  
    output(n)