Return to Revisions

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))