Given a binary circular array of size N, the task is to find the count maximum number of consecutive 1’s present in the circular array.
Examples:
Input: arr[] = {1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1}
Output: 6
The last 4 and first 2 positions have 6 consecutive ones.
Input: a[] = {0, 1, 0, 1, 0, 1, 0, 1, 0, 1}
Output: 1
A Naive Solution is create an array of size 2*N where N is size of input array. We copy the input array twice in this array. Now we need to find the longest consecutive 1s in this binary array in one traversal.
Efficient Solution : The following steps can be followed to solve the above problem:
- Instead of creating an array of size 2*N to implement the circular array, we can use the modulus operator to traverse the array circularly.
- Iterate from 0 to 2*N and find the consecutive number of 1’s as:
- Traverse array from left to right.
- Everytime while traversing, calculate the current index as (i%N) in order to traverse the array circularly when i>N.
- 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.
- Break out of the loop when a[i]==0 and i>=n to reduce the time complexity in some cases.
Below is the implementation of the above approach:
C++
// C++ program to count maximum consecutive// 1's in a binary circular array#include <bits/stdc++.h>using namespace std;// Function to return the count of maximum// consecutive 1's in a binary circular arrayint getMaxLength(bool arr[], int n){ // Starting index int start = 0; // To store the maximum length of the // prefix of the given array with all 1s int preCnt = 0; while (start < n && arr[start] == 1) { preCnt++; start++; } // Ending index int end = n - 1; // To store the maximum length of the // suffix of the given array with all 1s int suffCnt = 0; while (end >= 0 && arr[end] == 1) { suffCnt++; end--; } // The array contains all 1s if (start > end) return n; // Find the maximum length subarray // with all 1s from the remaining not // yet traversed subarray int midCnt = 0; // To store the result for middle 1s int result = 0; for (int i = start; i <= end; i++) { if (arr[i] == 1) { midCnt++; result = max(result, midCnt); } else { midCnt = 0; } } // (preCnt + suffCnt) is the subarray when // the given array is assumed to be circular return max(result, preCnt + suffCnt);}// 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); return 0;} |
Java
// Java program to count maximum consecutive// 1's in a binary circular arrayclass GfG { // Function to return the count of maximum // consecutive 1's in a binary circular array static int getMaxLength(int arr[], int n) { // Starting index int start = 0; // To store the maximum length of the // prefix of the given array with all 1s int preCnt = 0; while (start < n && arr[start] == 1) { preCnt++; start++; } // Ending index int end = n - 1; // To store the maximum length of the // suffix of the given array with all 1s int suffCnt = 0; while (end >= 0 && arr[end] == 1) { suffCnt++; end--; } // The array contains all 1s if (start > end) return n; // Find the maximum length subarray // with all 1s from the remaining not // yet traversed subarray int midCnt = 0; // To store the result for middle 1s int result = 0; for (int i = start; i <= end; i++) { if (arr[i] == 1) { midCnt++; result = Math.max(result, midCnt); } else { midCnt = 0; } } // (preCnt + suffCnt) is the subarray when // the given array is assumed to be circular return Math.max(result, preCnt + suffCnt); } // Driver code public static void main(String[] args) { int arr[] = new int[] { 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1 }; int n = arr.length; System.out.println(getMaxLength(arr, n)); }}// This code is contributed by Prerna Saini |
Python3
# Python 3 program to count maximum consecutive# 1's in a binary circular array# Function to return the count of # maximum consecutive 1's in a # binary circular arraydef getMaxLength(arr, n): # Starting index start = 0 # To store the maximum length of the # prefix of the given array with all 1s preCnt = 0 while(start < n and arr[start] == 1): preCnt = preCnt + 1 start = start + 1 # Ending index end = n - 1 # To store the maximum length of the # suffix of the given array with all 1s suffCnt = 0 while(end >= 0 and arr[end] == 1): suffCnt = suffCnt + 1 end = end - 1 # The array contains all 1s if(start > end): return n # Find the maximum length subarray # with all 1s from the remaining not # yet traversed subarray midCnt = 0 i = start # To store the result for middle 1s result = 0 while(i <= end): if(arr[i] == 1): midCnt = midCnt + 1 result = max(result, midCnt) else: midCnt = 0 i = i + 1 # (preCnt + suffCnt) is the subarray when # the given array is assumed to be circular return max(result, preCnt + suffCnt)# Driver codeif __name__ == '__main__': arr = [1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1] n = len(arr) print(getMaxLength(arr, n))# This code is contributed by# Surendra_Gangwar |
C#
// C# program to count maximum consecutive// 1's in a binary circular arrayusing System;class GFG { // Function to return the count of maximum // consecutive 1's in a binary circular array static int getMaxLength(int[] arr, int n) { // Starting index int start = 0; // To store the maximum length of the // prefix of the given array with all 1s int preCnt = 0; while (start < n && arr[start] == 1) { preCnt++; start++; } // Ending index int end = n - 1; // To store the maximum length of the // suffix of the given array with all 1s int suffCnt = 0; while (end >= 0 && arr[end] == 1) { suffCnt++; end--; } // The array contains all 1s if (start > end) return n; // Find the maximum length subarray // with all 1s from the remaining not // yet traversed subarray int midCnt = 0; // To store the result for middle 1s int result = 0; for (int i = start; i <= end; i++) { if (arr[i] == 1) { midCnt++; result = Math.Max(result, midCnt); } else { midCnt = 0; } } // (preCnt + suffCnt) is the subarray when // the given array is assumed to be circular return Math.Max(result, preCnt + suffCnt); } // Driver code public static void Main() { int[] arr = new int[] { 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0 }; int n = arr.Length; Console.WriteLine(getMaxLength(arr, n)); }}// This code is contributed by Code_Mech. |
Javascript
<script>// javascript program to count maximum consecutive// 1's in a binary circular array // Function to return the count of maximum // consecutive 1's in a binary circular array function getMaxLength(arr , n) { // Starting index var start = 0; // To store the maximum length of the // prefix of the given array with all 1s var preCnt = 0; while (start < n && arr[start] == 1) { preCnt++; start++; } // Ending index var end = n - 1; // To store the maximum length of the // suffix of the given array with all 1s var suffCnt = 0; while (end >= 0 && arr[end] == 1) { suffCnt++; end--; } // The array contains all 1s if (start > end) return n; // Find the maximum length subarray // with all 1s from the remaining not // yet traversed subarray var midCnt = 0; // To store the result for middle 1s var result = 0; for (i = start; i <= end; i++) { if (arr[i] == 1) { midCnt++; result = Math.max(result, midCnt); } else { midCnt = 0; } } // (preCnt + suffCnt) is the subarray when // the given array is assumed to be circular return Math.max(result, preCnt + suffCnt); } // Driver code var arr = [ 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1 ]; var n = arr.length; document.write(getMaxLength(arr, n));// This code is contributed by umadevi9616 </script> |
Output
6
Time Complexity: O(N), as we are using a loop to traverse N times. Where N is the number of elements in the array.
Auxiliary Space: O(1), as we are not using any extra space.
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!
