Count Minimum Right Flips to Set All Values in an Array in C++

We are given an array of 0s and 1s which represent the state of bulbs that are connected with the same wire in sequence. 0 represents that the bulb is OFF and 1 represents that the bulb is ON. For such a sequence of N bulbs, if the switch of the bulb is pressed then all bulbs on right, (i+1 th till n) change their previous stare, from ON to OFF or from OFF to ON.

For the given state of all bulbs, the goal is to find the minimum switches to be pressed to turn all of them ON. [ the same switch can be pressed any number of times ]. It is the same as flipping the state of right index values in an array to set all of them as 1.

Input

Bulbs[]= { 1,0,1,0 }

Output

Minimum right flips: 3

Explanation

Original state 1010

Press switch 2:- 1:101 flip count=1
Press switch 3:- 11:10 flip count=2
Press switch 4:- 111:1 flip count=3

Input

Bulbs[]= { 1,0,0,0 }

Output

Minimum right flips: 1

Explanation

Original state 1000
Press switch 2:- 1:111 flip count=1

All bulbs on right turned ON.

Approach used in the below program is as follows

• Integer stores the state of N number of bulbs.

• Function minFlips(int arr[],int n) takes an array and its length n as input and returns the minimum count of right flips to set values of array ( turn all off bulbs on )

• Variable count is used to store the number of flips, initially 0.

• Array switch[] is used to store the initial state of all switches corresponding to i th bulb. All are 0 ( switch[]={0}.)

• Starting from i=0 to n we do following −

  • If bulb is ON and switch is off, do nothing (increase i)

  • If bulb is OFF and switch is on, do nothing (increase i) as turning switch off will do nothing to bulb’s state

  • If bulb is OFF and switch is off, increase count and turn state of all bulbs on the right. ( while loop )

• After the end of for loop return the result present in ‘count’ as flips done.

• Return count.

Example

 Live Demo

// C++ program to find minimum number of move-to-front
// moves to arrange items in sorted order.
#include <bits/stdc++.h>
using namespace std;
// Calculate minimum number of moves to arrange array
// in increasing order.
int minFlips(int arr[], int n){
   int count = 0;
   int swich[n] = {0}; //Initially we don't flip the states, so flip is false
   for(int i=0;i<n;i++){
      if(arr[i]==1 && swich[i]==0)
         i++;
      if(arr[i]==0 && swich[i]==1)
         i++;
      if(arr[i]==0 && swich[i]==0){
         count++;
         int j=i;
      while(j<n){
         if(arr[j]==0)
            arr[j++]=1;
         else
            arr[j++]=0;
         }
      }
   }
   return count;
}
int main(){
   int Arr[] = {0,1,0,1};
   int N = 4;
   cout <<”Minimum right flips to set all values in an array:"<<
   minFlips(Arr, N);
   return 0;
}

Output

Minimum right flips to set all values in an array: 4