Coding Ninja || Flip Bits C++ Solution

 

Problem Statement

    Level: easy

You are given an array of integers ARR[] of size N consisting of zeros and ones. You have to select a subset and flip bits of that subset. You must return the count of maximum ones you can obtain by flipping chosen sub-array at most once.

A flip operation is one in which you turn 1 into 0 and 0 into 1

Approach:

•  The Approach is simple. It's just another example of Kadence's algorithm. Let me show you how it is:
• We will first create some variables;

1.  maxCount - This will store the maximum continues zeros.
2.  Count -  We will increase this count every time we get a zero. and if we get a '1' we will save this count to maxCount and make it zero.
3.  maxOne; - thsi wiill store the count of the 1 that are already present.

• Run a for loop for arr.Size elements, and if the value is zero, iterate the count by 1.
• if it is not zero(i.e., 1), then decrease the count by 1. and increase the maxOne count by 1. 
• If the count goes negative (i.e. count < 0), then make the count zero. ( 💡 You can recall the kadanes' algorithm here).
• Finally, return the sum of the maximum zero subarrays (i..e. maxCount) and the count of the maxOne,

CODE:-

---

int flipBits(int* arr, int n) { // WRITE YOUR CODE HERE int count=0, maxcount=0, x=0; for(int i=0; imaxcount) maxcount=count; if(count<0) count=0; } return maxcount+x; }

---

Time Complexity:- O(n)

Space Complexity:- O(1) 

   that

Ti