Given binary array, find count of maximum number of consecutive 1’s present in the array.
Examples :
Input : arr[] = {1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1}
Output : 4
Input : arr[] = {0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1}
Output : 1
A simple solution is consider every subarray and count 1’s in every subarray. Finally return size of largest subarray with all 1’s. An efficient solution is traverse array from left to right. If we see a 1, we increment count and compare it with maximum so far. If we see a 0, we reset count as 0.
Implementation:
CPP
// C++ program to count maximum consecutive// 1's in a binary array.#include<bits/stdc++.h>using namespace std;// Returns count of maximum consecutive 1's// in binary array arr[0..n-1]int getMaxLength(bool arr[], int n){ int count = 0; //initialize count int result = 0; //initialize max for (int i = 0; i < n; i++) { // Reset count when 0 is found if (arr[i] == 0) count = 0; // If 1 is found, increment count // and update result if count becomes // more. else { count++;//increase count result = max(result, count); } } return result;}// Driver codeint main(){ bool arr[] = {1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1}; int n = sizeof(arr)/sizeof(arr[0]); cout << getMaxLength(arr, n) << endl; return 0;} |
Java
// Java program to count maximum consecutive// 1's in a binary array.class GFG { // Returns count of maximum consecutive 1's // in binary array arr[0..n-1] static int getMaxLength(boolean arr[], int n) { int count = 0; //initialize count int result = 0; //initialize max for (int i = 0; i < n; i++) { // Reset count when 0 is found if (arr[i] == false) count = 0; // If 1 is found, increment count // and update result if count becomes // more. else { count++;//increase count result = Math.max(result, count); } } return result; } // Driver method public static void main(String[] args) { boolean arr[] = {true, true, false, false, true, false, true, false, true, true, true, true}; int n = arr.length; System.out.println(getMaxLength(arr, n)); }}// This code is contributed by Anant Agarwal. |
Python3
# Python 3 program to count # maximum consecutive 1's # in a binary array.# Returns count of maximum # consecutive 1's in binary# array arr[0..n-1]def getMaxLength(arr, n): # initialize count count = 0 # initialize max result = 0 for i in range(0, n): # Reset count when 0 is found if (arr[i] == 0): count = 0 # If 1 is found, increment count # and update result if count # becomes more. else: # increase count count+= 1 result = max(result, count) return result # Driver codearr = [1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1] n = len(arr) print(getMaxLength(arr, n))# This code is contributed by Smitha Dinesh Semwal |
C#
// C# program to count maximum // consecutive 1's in a binary array.using System;class GFG { // Returns count of maximum consecutive // 1's in binary array arr[0..n-1] static int getMaxLength(bool []arr, int n) { int count = 0; //initialize count int result = 0; //initialize max for (int i = 0; i < n; i++) { // Reset count when 0 is found if (arr[i] == false) count = 0; // If 1 is found, increment count // and update result if count // becomes more. else { count++; //increase count result = Math.Max(result, count); } } return result; } // Driver code public static void Main() { bool []arr = {true, true, false, false, true, false, true, false, true, true, true, true}; int n = arr.Length; Console.Write(getMaxLength(arr, n)); }}// This code is contributed by Nitin Mittal. |
Javascript
<script>// JavaScript program to count maximum// consecutive 1's in a binary array.// Returns count of maximum// consecutive 1's in binary// array arr[0..n-1]function getMaxLength(arr, n) { // initialize count let count = 0; // initialize max let result = 0; for (let i = 0; i < n; i++) { // Reset count when 0 is found if (arr[i] == 0) count = 0; // If 1 is found, increment // count and update result // if count becomes more. else { // increase count count++; result = Math.max(result, count); } } return result;}// Driver codelet arr = new Array(1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1);let n = arr.length;document.write(getMaxLength(arr, n));// This code is contributed by gfgking</script> |
PHP
<?php// PHP program to count maximum // consecutive 1's in a binary array.// Returns count of maximum // consecutive 1's in binary // array arr[0..n-1]function getMaxLength($arr, $n){ // initialize count $count = 0; // initialize max $result = 0; for ($i = 0; $i < $n; $i++) { // Reset count when 0 is found if ($arr[$i] == 0) $count = 0; // If 1 is found, increment // count and update result // if count becomes more. else { // increase count $count++; $result = max($result, $count); } } return $result;}// Driver code$arr = array(1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1);$n = sizeof($arr) / sizeof($arr[0]);echo getMaxLength($arr, $n) ;// This code is contributed by nitin mittal.?> |
Output
4
Time Complexity : O(n)
Auxiliary Space : O(1)
Approach 2:
Another approach to solve this problem is to use the bitwise AND operation to count the number of consecutive 1’s in the binary representation of the given number. We iterate over the bits of the number from the right and use a mask to check the value of each bit. If the bit is 1, we increment a counter. If the bit is 0, we reset the counter to zero. We update the maxCount if the counter is greater than maxCount.
Here’s the implementation of the above approach in C++:
C++
#include <iostream>#include <vector>using namespace std;int maxConsecutiveOnes(vector<int>& nums) { int max_count = 0, current_count = 0, mask = 0; for (int i = 0; i < nums.size(); i++) { if (nums[i] == 1) { mask = (mask << 1) | 1; } else { mask = mask << 1; } if ((nums[i] & mask) != 0) { current_count++; } else { max_count = max(max_count, current_count); current_count = 0; mask = 0; } } max_count = max(max_count, current_count); return max_count;}int main() { vector<int> nums = {1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1}; int max_ones = maxConsecutiveOnes(nums); cout << "Maximum consecutive ones: " << max_ones << endl; return 0;} |
Python3
# Function to find the maximum number of consecutive ones in a binary arraydef max_consecutive_ones(nums): max_count = 0 # Initialize the maximum consecutive ones count to 0 current_count = 0 # Initialize the current consecutive ones count to 0 mask = 0 # Initialize a mask to keep track of consecutive ones for num in nums: # Iterate through the elements in the array if num == 1: mask = (mask << 1) | 1 # Shift the mask one position left and set the rightmost bit to 1 else: mask = mask << 1 # Shift the mask one position left (rightmost bit becomes 0) if (num & mask) != 0: # Check if the bitwise AND of the current element # and the mask is not 0 current_count += 1 # If there is a consecutive one, increment the current count else: max_count = max(max_count, current_count) # Update the maximum count if necessary current_count = 0 # Reset the current count to 0 mask = 0 # Reset the mask to 0 max_count = max(max_count, current_count) # Update the maximum count after the loop return max_count# Main functiondef main(): nums = [1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1] max_ones = max_consecutive_ones(nums) # Find the maximum consecutive ones print("Maximum consecutive ones:", max_ones)if __name__ == "__main__": main() |
Output
Maximum consecutive ones: 4
Time Complexity: O(logn), where n is the decimal representation of the given number.
Space Complexity: O(1).
Exercise:
Maximum consecutive zeros in a binary array.
This article is contributed by Smarak Chopdar. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
