Find Zeros to be Flipped so that number of Consecutive 1’s is maximized in C
Find Zeros to be Flipped so that number of Consecutive 1’s is maximized in C
In this page we will look into a coding question where we will learn how to find the zeros that needs to be flipped so that the number of consecutive 1’s is maximized
The problem revolves around analyzing a binary array (an array containing only 0s and 1s) and determining how flipping a limited number of zeros can yield the longest contiguous sequence of 1s. This has practical applications in signal processing, data compression, and even certain AI models where pattern detection is involved.
Find Zeros to be Flipped so that number of Consecutive 1’s is maximized in C
Here are the step-by-step instructions to solve this problem:
- Initialize two pointers left and right to the beginning of the array.
- Initialize a variable zero_count to keep track of the number of zeroes seen so far and another variable max_ones to keep track of the maximum number of consecutive ones seen so far.
- Move the right pointer to the right until we reach a zero. At this point, increment zero_count.
- If zero_count is greater than m, move the left pointer to the right until we have flipped the required number of zeroes (i.e., zero_count – m). Update zero_count accordingly.
- Update max_ones to be the maximum of its current value and the length of the current sequence of ones (i.e., right – left + 1).
- Repeat steps 3-5 until the end of the array is reached.
- Return max_ones.
Brute Force Approach
#includeint findMaxConsecutiveOnes(int arr[], int n) { int maxCount = 0; // Try flipping each zero one by one and count the consecutive 1's for (int i = 0; i < n; i++) { if (arr[i] == 0) { arr[i] = 1; // Flip 0 to 1 // Count maximum consecutive 1s now int count = 0, maxConsec = 0; for (int j = 0; j < n; j++) { if (arr[j] == 1) count++; else count = 0; if (count > maxConsec) maxConsec = count; } // Update result if (maxConsec > maxCount) maxCount = maxConsec; arr[i] = 0; // Revert the flip } } return maxCount; } int main() { int arr[] = {1, 0, 1, 1, 0, 1, 1, 1}; int n = sizeof(arr) / sizeof(arr[0]); int result = findMaxConsecutiveOnes(arr, n); printf("Maximum consecutive 1s after flipping one 0: %d\n", result); return 0; }
Output:
Maximum consecutive 1s after flipping one 0: 6
Explanation:
Loop through each element:
If it’s 0, flip it to 1.
Count the maximum consecutive 1s using another loop.
Restore the array by flipping back the 1 to 0.
Keep track of the maximum number of 1s found in all iterations.
In the example {1, 0, 1, 1, 0, 1, 1, 1},
flipping the 0 at index 4 gives the longest streak:
1 0 1 1 [1] 1 1 1 → 6 consecutive 1s.
Time & Space Complexity:
- O(n²) — because for each element (in worst case all n elements), we traverse the array again to count consecutive 1s.
- No extra space used: O(1)
Program to find zeros to be flipped so that binary number is maximized in C
#include <stdio.h>
int max (int a, int b)
{
return a > b ? a : b;
}
int find_zeroes_to_flip (int arr[], int n, int zeros)
{
int left = 0, right = 0, zero_count = 0, max_ones = 0;
while (right < n) { if (arr[right] == 0) { zero_count++; } while (zero_count > zeros)
{
if (arr[left] == 0)
{
zero_count--;
}
left++;
}
max_ones = max (max_ones, right - left + 1);
right++;
}
return max_ones;
}
int main ()
{
int arr[] = { 1, 0, 1, 0, 1, 1, 0, 1, 1, 1 };
int n = sizeof (arr) / sizeof (arr[0]);
int zeros = 1;
int max_consecutive_ones = find_zeroes_to_flip (arr, n, zeros);
printf ("Max consecutive ones after flipping %d zeroes: %d\n", zeros,
max_consecutive_ones);
return 0;
}
Output:
Max consecutive ones after flipping 1 zeroes: 6
Explanation:
- Uses Sliding Window: Tracks a window with at most the allowed number of 0s to flip.
- Max Count Update: Updates the maximum length of 1s (right – left + 1) during traversal.
- Efficient Approach: Runs in O(n) time, ideal for large binary arrays.
Wrapping Up:
This problem demonstrates an efficient way to find the maximum number of consecutive 1’s by flipping a limited number of 0’s in a binary array. The sliding window approach helps in solving the problem with optimal time complexity.
Understanding this logic enhances your array and window technique skills in C. You can modify this logic for variations like tracking the actual positions of flipped zeros as well.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
FAQs
The sliding window method is the most efficient approach, providing a linear time complexity of O(n) and constant space.
Yes, by storing the indices of 0s during traversal, we can backtrack and identify which positions were part of the longest valid window.
The time complexity is O(n), and the space complexity is O(1), making it ideal for large arrays.
Yes, the code works for any value of zeros (i.e., allowed flips). You can simply change the zeros variable to fit your requirement.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment