# Minimum lights to activate

Jan 22nd, 2022
1,309
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. int Solution::solve(vector<int> &A, int B) {
2.     int n = A.size();
3.     int count = 0;
4.     for(int i=0; i< n; i++){
5.         //We will follow greedy approach.
6.         //We will go the rightmost light which can light up the current location.
7.         int next = i+B-1;
8.         int prev = max(0,i-B+1); //We set the minimum to 0 so that when we do A[prev] prev is not a negative number
9.         int idx = next; // Going to the rightmost position that can light up the current location.
10.         bool flag = false; // Boolean to identify if it is possible to light up i at all
11.         while(idx>=prev){ //prev to idx are the locations that can light up i
12.             if(A[idx]){
13.                 count++;
14.                 flag = true; // It is possible to light up i
15.                 i = idx+B-1; //This light will be able to light up locations upto idx+B-1
16.                 break; //You have lighted up the ith position. So no need of this while loop anymore
17.             }
18.             idx--;
19.         }
20.         if(!flag)return -1; //It is not possible to light up the entire street whatsoever.
21.     }
22.     return count;
23. }