Minimum Lights to Activate

There is a corridor in a Jail which is N units long. Given an array A of size N. The ith index of this array is 0 if the light at ith position is faulty otherwise it is 1.

All the lights are of specific power B which if is placed at position X, it can light the corridor from [ X-B+1, X+B-1].

Initially all lights are off.

Return the minimum number of lights to be turned ON to light the whole corridor or -1 if the whole corridor cannot be lighted.

Note: using language=C++;

Solution:

The input is in the following format:

int n;
scanf("%d", &n);
int lights[n];
for( int i=0; i<n; i++ )
    scanf("%d", &lights[i]);
int size;
scanf("%d", &size);

In the example I am showing, I have changed the name of the array from A to lights and changed the name of the variable B to size.

Usually while solving problems, try converting or transforming the problem to a different form or way. This will usually simplify the problem. One idea that comes to my mind when I read this problem is converting this into pairs of ranges which the light lights. For that we can do:

vector<pair<int, int> > lightable;
for( int i=0; i<n; i++ ) {
    if( lights[i] == 1 )
        lightable.push_back({max(0, i-size+1), min(n-1, i+size-1)});
}

Let’s create a variable lightsSize = lights.size(); for convenience.

Checking some edge cases:

// When there are no lights
if( lightableSize == 0 ) return -1;
// When the first light is not lightable
if( lightable[0].first != 0 ) return -1;
// When the last light is not lightable
if( lightable[lightableSize-1].second != n-1 ) return -1;

To capture the light upto which we are covered, we use a variable called int currentCovered = -1; and to capture the minimum number of lights required, we use a variable int minimumNumberOfLights = 0;

Let us iterate through the lightable array until we reach the penultimate element.

for( int i=0; i<lightableSize-1; i++ ) {
    // If the current light is already covered, then do nothing
    // If the current light can cover the next light which has not yet covered
    if( lightable[i].first == currentCovered+1 ) {
        currentCovered = lightable[i].second;
        minimumNumberOfLights++;
    }
    // If the light can not cover the next light which has not been covered 
    else if ( lightable[i].first > currentCovered+1 ) return -1;
    // If the next light does not cover the next light which can not be covered
    else if( lightable[i+1].first > currentCovered+1 ) {
        currentCovered = lightable[i].second;
        minimumNumberOfLights++;
    }
    
    // If the next light is covering the same light as the current light
    if( lightable[i].first == lightable[i+1].first )
        currentCovered = lightable[i+1].second;
}

Check if the last light is coverable:

if( currentCovered+1 < lightable[lightableSize-1].first ) return -1;
else if( currentCovered < lightable[lightableSize-1].second ) minimumNumberOfLights++;

Thats it! Now the minimum number of lights required will be stored in the variable minimumNumberOfLights .

Full Code:

int minimumNumberOfLightsRequired(vector<int> &lights, int size) {
int n=lights.size();
vector<pair<int, int> > lightable;
for( int i=0; i<n; i++ ) {
    if( lights[i] == 1 )
        lightable.push_back({max(0, i-size+1), min(n-1, i+size-1)});
}
int lightableSize = lightable.size();
if( lightableSize == 0 ) return -1;
if( lightable[0].first != 0 ) return -1;
if( lightable[lightableSize-1].second != n-1 ) return -1;
int currentCovered = -1, minimumNumberOfLights = 0, previousCoverage;
for( int i=0; i<lightableSize-1; i++ ) {
    if ( lightable[i].first == currentCovered+1 ) {
        currentCovered = lightable[i].second;
        minimumNumberOfLights++;
    } else if( lightable[i].first > currentCovered+1 ) return -1;
    else if( lightable[i+1].first > currentCovered+1 ) {
        currentCovered = lightable[i].second;
        minimumNumberOfLights++;
    }
    if( lightable[i].first == lightable[i+1].first )
         currentCovered = lightable[i+1].second;
}
if( currentCovered+1 < lightable[lightableSize-1].first ) return -1;
else if( currentCovered < lightable[lightableSize-1].second) minimumNumberOfLights++;
return minimumNumberOfLights;
}