Advertisement
Lokesh04

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. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement