Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int Solution::solve(vector<int> &A, int B) {
- int n = A.size();
- int count = 0;
- for(int i=0; i< n; i++){
- //We will follow greedy approach.
- //We will go the rightmost light which can light up the current location.
- int next = i+B-1;
- 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
- int idx = next; // Going to the rightmost position that can light up the current location.
- bool flag = false; // Boolean to identify if it is possible to light up i at all
- while(idx>=prev){ //prev to idx are the locations that can light up i
- if(A[idx]){
- count++;
- flag = true; // It is possible to light up i
- i = idx+B-1; //This light will be able to light up locations upto idx+B-1
- break; //You have lighted up the ith position. So no need of this while loop anymore
- }
- idx--;
- }
- if(!flag)return -1; //It is not possible to light up the entire street whatsoever.
- }
- return count;
- }
Advertisement
Advertisement
Advertisement
RAW Paste Data
Copied
Advertisement