17
\$\begingroup\$

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)
\$\endgroup\$
  • 5
    \$\begingroup\$ Your instinct is quite right. There is no need to convert numbers to strings in order to work with binary. The trap that you and most of other answers (included the accepted one) fall in, is not knowing how to work with binary numbers. See Anatolii's answer for what the normal, more efficient (albeit very commonly unknown) approach is. \$\endgroup\$ – Gnudiff Dec 27 '19 at 7:26
  • 2
    \$\begingroup\$ This task is a good exercise, but since people re bringing up efficiency, I think it's worth mentioning that newer processors have this built in to the hardware. \$\endgroup\$ – Ryan1729 Dec 28 '19 at 2:30
13
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 4
    \$\begingroup\$ I know this is not meant to be codegolfed, but your return line can be written shorter as return len(max(bin_num.split('0'))) \$\endgroup\$ – Zchpyvr Dec 25 '19 at 16:20
  • 3
    \$\begingroup\$ @Zchpyvr, I would not consider that as better approach. Consider this case: bin(18888889)[2:].split('0') that generates ['1', '', '1', '', '', '', '', '', '', '111', '', '', '1', '111', '', '1'] , a list of 16 items for further traversal. While the former approach returns a list of 6 items. \$\endgroup\$ – RomanPerekhrest Dec 25 '19 at 16:45
  • 6
    \$\begingroup\$ using re: max(re.split(r'0+', bin(18888889)[2:])). >> it's harder to read. If no performance gain, code should aim for maximal readability. Code is a human machine interface after all \$\endgroup\$ – Poutrathor Dec 25 '19 at 22:07
  • 3
    \$\begingroup\$ @RomanPerekhrest Oh :) I did not believe him (nor do I believe you, yet). I merely wrote a polite answer awaiting the time I could test it myself and asking "compared to" [which implementation] such an improvement was measured. For one, you tested only one number 188888889000. \$\endgroup\$ – Poutrathor Dec 26 '19 at 10:11
  • 2
    \$\begingroup\$ Using strings to manipulate numbers strikes me as incredibly inelegant. \$\endgroup\$ – Voo Dec 27 '19 at 21:14
21
\$\begingroup\$

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)
         &
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))
| improve this answer | |
\$\endgroup\$
  • 6
    \$\begingroup\$ It's possible this is less efficient in Python, given that it has to loop maxLength times. Python interpreter overhead is notoriously high. But IDK how much time cost there is for converting to strings or lists of digits and pattern-matching on those (which amounts to running compiled C functions in the Python interpreter, if we're talking about CPython). But yes, algorithmically O(result) is better than O(input_bits), and vastly better than O(input_bits^2) for large inputs, and this would be blazing fast in a compiled language, e.g. Cython or PyPy, or of course C. \$\endgroup\$ – Peter Cordes Dec 27 '19 at 9:18
  • 2
    \$\begingroup\$ @Peter Even more worrisome: If this is an arbitrary large number, is the interpreter clever enough to optimize number = number & left_shifted_number to make it in-place? Otherwise the performance will be quadratic and awful. Even then the shifting would lead to O(n log n) runtime behavior for arbitrary precision numbers I think. For fixed length numbers this is great though. \$\endgroup\$ – Voo Dec 27 '19 at 21:16
15
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ to_binary = '{:b}'.format is simpler than using bin to add 0b then removing it again. to_binary = lambda x: format(x, 'b') also works, and avoids some string parsing. \$\endgroup\$ – Eric Dec 26 '19 at 11:37
  • 2
    \$\begingroup\$ @Eric What about def to_binary(x): return f'{x:b}'? \$\endgroup\$ – Solomon Ucko Dec 26 '19 at 17:52
  • \$\begingroup\$ @SolomonUcko Directly invoking format might be better, because it does not need to parse the f-string. Some profiling would be needed there as well, though. In addition, it means requiring Python 3.6, which may or may not be a concern. \$\endgroup\$ – Graipher Dec 26 '19 at 21:04
  • \$\begingroup\$ @Graipher Aren't f-strings are parsed at compile time? I'll investigate more when I get a chance. \$\endgroup\$ – Solomon Ucko Dec 26 '19 at 21:09
  • 3
    \$\begingroup\$ @Graipher At least for me, f-strings result in direct usage of the FORMAT_VALUE bytecode instruction, instead of loading and calling format, which uses LOAD_GLOBAL then CALL_FUNCTION, which is almost certainly significantly slower. \$\endgroup\$ – Solomon Ucko Dec 26 '19 at 21:40
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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)   
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Usually alternative implementations are not considered valid answers if they don't contain a review. After all, this is Code Review, not Code Alternatives. However, since you specifically move toward in-built functions and your code is much shorter, the review is implied. But please keep that in mind next time. Welcome to Code Review! \$\endgroup\$ – Mast Jun 1 at 9:53
  • 1
    \$\begingroup\$ Do note that if I ever find constructs like yours in production code, I'd delete it outright. That last line of your output function is abysmal. There is way too much happening on a single line, hurting readability and maintainability. If you go the route of oneliners, perhaps putting it in some kind of generator function would be more appropriate. \$\endgroup\$ – Mast Jun 1 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.