# Minimum Light Bulbs Needed To Light The Whole Corridor

Given :

• An array of N cell(s) in a jail.
• Each cell has a working bulb denoted by 1 and a faulty bulb denoted by 0.
• Power of each bulb is P.
A bulb with power P at position X can light cells in range [ X - P + 1, …, X + P - 1 ]
• Initially all bulbs are switched OFF.

Objective : Return the minimum number of lights that should be switched ON to light the whole corridor. Return -1 if the whole corridor cannot be lighted.

Consider the below example:
Power of each bulb is 3.
Bulbs in cells [ 2, 3, 4 ] are in working condition. ``````#include<iostream>
#include<vector>

using namespace std;

int solve (vector<int> &jail, int power) {

int cells = jail.size();
int count = 0;
int pos = 0;
bool lit = false;

while (pos < cells) {

lit = false;
int from_right = min (cells-1, pos + power - 1);
int from_left =  max (0, pos - power + 1);

// Check from right
for (int cell_no = from_right; cell_no >= pos; cell_no--) {
if (A[cell_no] == 1) {
count++;
pos = cell_no + power; // new pos of the next cell to be lit.
lit = true;
break;
}
}

if (!lit) {
// Check from left;
for (int cell_no = pos-1; cell_no >= from_left; cell_no--) {
if (A[cell_no] == 1) {
count++;
pos = cell_no + power; // new pos of the next cell to be lit.
lit = true;
break;
}
}
}

if (!lit)
return -1;
}
return count;
}

int main() {

vector<int> jail1 = {0, 0, 1, 1, 1, 0, 0};
cout << "Bulbs switched on : " << solve(jail1, 3) << endl;

vector<int> jail2 = {1, 1, 1};
cout << "Bulbs switched on : " << solve(jail2, 3) << endl;

vector<int> jail3 = {0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0};
cout << "Bulbs switched on : " << solve(jail3, 12) << endl;

vector<int> jail4 = {0, 1, 0};
cout << "Bulbs switched on : " << solve(jail4, 1) << endl;

return 0;
}
``````

Output

``````Bulbs switched on : 2
Bulbs switched on : 1
Bulbs switched on : 2
Bulbs switched on : -1
``````