Posts Longest Consecutive 1's (geeksforgeeks - SDE Sheet)
Post
Cancel

Longest Consecutive 1's (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Given a number N. Find the length of the longest consecutive 1s in its binary representation.

geeksforgeeks

SOLUTION

APPROACH 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution{

    public static int maxConsecutiveOnes(int n) {

        int max = 0;
        int current = 0;

        while(n != 0){

            if((n&1) != 0){
                current++;
            }else{
                current = 0;
            }

            max = Math.max(max, current);

            n = n >> 1;

        }

        return max;

    }
}

APPROACH 2

By taking the bitwise AND (&) of N and N left-shifted by 1, we effectively “erase” the trailing 1 from every sequence of consecutive 1s. This reduces the number of consecutive 1s in each iteration, helping us count their length.

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

    public static int maxConsecutiveOnes(int n) {

        int count = 0;

        while(n != 0){

            n = (n & (n << 1)); // right shift would also work with the same logic
            count++;

        }

        return count;

    }
}
This post is licensed under CC BY 4.0 by the author.