Problem

Given an integer n, return the length of the longest consecutive run of 1s in its binary representation.

Examples

Example 1

1
2
3

Input: n = 156
Output: 3
Explanation: The binary representation of 156 is "10011100". The longest run of consecutive `1`s is "111", which has a length of 3.

Example 2

1
2
3

Input: n = 13
Output: 2
Explanation: The binary representation of 13 is "1101". The longest run of consecutive `1`s is "11", which has a length of 2.

Solution

Method 1 - Convert to binary string

To find the longest consecutive sequence of 1s in the binary representation of an integer:

  1. Convert the integer to its binary representation.
  2. Traverse the binary string to count the length of consecutive 1s.
  3. Keep track of the maximum length encountered during the traversal.

Approach

  1. Convert the integer n to its binary representation using bin(n)[2:].
  2. Initialize a counter to track the current run of 1s and a variable to store the maximum length.
  3. Iterate through the binary string and update the current run length and the maximum length as necessary.
  4. Return the maximum length after traversal.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public class Solution {
    public int longestConsecutiveOnes(int n) {
        String binaryString = Integer.toBinaryString(n);
        int maxLength = 0, currentLength = 0;
        
        for (char c : binaryString.toCharArray()) {
            if (c == '1') {
                currentLength++;
                maxLength = Math.max(maxLength, currentLength);
            } else {
                currentLength = 0;
            }
        }
        
        return maxLength;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def longestConsecutiveOnes(self, n: int) -> int:
        binary_string = bin(n)[2:]
        max_length = 0
        current_length = 0
        
        for char in binary_string:
            if char == '1':
                current_length += 1
                max_length = max(max_length, current_length)
            else:
                current_length = 0
                
        return max_length

Complexity

  • ⏰ Time complexity: O(b), where b is the number of bits in the binary representation of n.
  • 🧺 Space complexity: O(1), for the variables tracking the run length and maximum length.