Length of the longest run of consecutive 1s in binary representation
Filed under Paytm
Free read 3 of 3Confirm n is non-negative and what to return for 0 (zero). Ask about the integer width if the language has fixed-size ints.
The question
Given a non-negative integer n, return the length of the longest run of consecutive 1 bits in its binary representation. For example 14 is 1110, so the answer is 3.
Constraints
- 0 <= n < 2^31
Examples
- Input
- n = 14
- Output
- 3
- Why
- Binary 1110 has a run of three 1s.
- Input
- n = 5
- Output
- 1
- Why
- Binary 101 never has two 1s in a row.
Approach
Confirm n is non-negative and what to return for 0 (zero). Ask about the integer width if the language has fixed-size ints.
Walk through the bits with n & 1 and n >>= 1, keeping a current run counter that resets on a 0 and a best value that tracks the maximum. O(log n).
The operation n &= (n << 1) shortens every run of 1s by one. Repeat until n becomes 0 and count the iterations; that count equals the longest run.
n = 0 gives 0, n = 1 gives 1, all-ones numbers like 15 give the bit length, and a run at the least or most significant end must still be counted.
Solution
O(L) time where L is the longest run (at most the bit length), O(1) space
def longest_ones(n):
best = 0
while n:
n &= n << 1 # each pass shortens every run of 1s by one
best += 1
return best
Tips
- What they are testing: Basic bit manipulation fluency: shifting, masking, and a clean loop with a reset counter.
- Common mistake: Forgetting to update the best value after the final bit, so a run that ends at the top bit is missed.
Related Paytm questions
Collected from public candidate posts and coding forums. Updated Nov 2026.