Maximum consecutive one’s in a binary array

Find the maximum consecutive 1's in an array of 0's and 1's. And Find length of the longest consecutive One's in binary representation.

---

Given a binary array, find the maximum number of consecutive 1s in this array or find the maximum consecutive 1's in an array of 0's and 1's.

Lets understand what is the input and the expected output.

Algorithm (Find the maximum consecutive 1's in an array of 0's and 1's.)

---

Iterate the array and increment the counter when we encounter 1, when we encounter 0, this is the time we already checked one instance of consecutive ones, update maxCount if it the count of 1's is greater than maxCount encountered till now. 

Maximum consecutive one’s in a binary array in Java

---

package com.javabypatel.misc;

/*

Input: [1,1,0,1,0,1,1,1]
Output: 3

Input: [1,0,1,0,1,0,1,0]
Output: 1

Input: [1,1,1,1]
Output: 4

 */
public class MaxConsecutiveOnes {

    public static void main(String[] args) {
        //int[] arr = new int[] {1, 1, 0, 1, 0, 1, 1, 1};
        int[] arr = new int[] {1, 0, 1, 0};

        System.out.println(findMaximumOnes(arr));
    }

    private static int findMaximumOnes(int[] arr) {

        int count = 0;
        int maxCount = 0;

        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == 1) {
                count += 1;
            } else {
                count = 0;
            }
            maxCount = count > maxCount ? count : maxCount;
        }
        return maxCount;
    }
}

Algorithm (Find length of the longest consecutive One's in binary representation.)

---

Input : number = 13 (binary representation = 1101)
Output : 2 (max consecutive one is 2)

Input : number = 20 (binary representation = 10100)
Output : 1 (max consecutive one is 1)

We will use Bit manipulation to count the longest sequence of consecutive ones.
we will do logical AND between number and number >> 1 until number become 0, the number of iteration required for number to become 0 will be longest consecutive sequence of ones.

Lets understand how,

number = 59 (binary = 111011)
number >> 1 (binary = 011101)

If you see, when we do AND between number and number>>1, the first bit of all the sequences of ones that are present in binary representation of number becomes 0.
number = 59 = 1 1 1 0 1 1  (first bit in sequences of ones (1 1 1) and (1 1))


Iteration 1:

logical AND between 59 and 59 >> 1,
1 1 1 0 1 1
0 1 1 1 0 1 &
---------------------------
0 1 1 0 0 1 = number

First bit in sequences of 1's become 0

Iteration 2:

number = 0 1 1 0 0 1

logical AND between  0 1 1 0 0 1 and (0 1 1 0 0 1 >> 1)
0 1 1 0 0 1
0 0 1 1 0 0 &
-----------------------------
0 0 1 0 0 0 = number

Again first bit in sequences of 1's become 0

Iteration 3:

number = 0 0 1 0 0 0

logical AND between  0 0 1 0 0 0 and (0 0 1 0 0 0 >> 1)            
0 0 1 0 0 0
0 0 0 1 0 0 &
-----------------------------
0 0 0 0 0 0 = number

Again first bit in sequences of 1's become 0

Total 3 iteration required for number to become 0 and that is the longest consecutive sequence of 1 present.

package com.javabypatel.misc;

class FindLengthOfLongestConsecutiveOnes {

    public static void main(String[] args) {
        int number = 59;
        System.out.println(findMaximumOnes(number));
    }
    
    private static int findMaximumOnes(int number) {
        int count = 0;
        while(number != 0) {
            number = number & (number << 1);
            count++;
        }
        return count;
    }
}

You may also like to see

---

Sort Linked list using Merge sort

Bubble Sort

Heap Sort

Selection Sort

Insertion Sort

---

How ConcurrentHashMap works and ConcurrentHashMap interview questions

How Much Water Can A Bar Graph with different heights can Hold

Interview Questions-Answer Bank

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.