Minimum Lights To Activate
Vložit
- čas přidán 28. 07. 2024
- Timestamps:
0:00 Reading the problem
0:55 Example 1
2:35 Example 2
3:15 Example 3
4:25 Intuition and Logic Building
9:30 Final Example
12:50 Code
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.
Input Format
First argument is an integer array A where A[i] is either 0 or 1.
Second argument is an integer B.
Output Format
Return the minimum number of lights to be turned ON to light the whole corridor or -1 if the whole corridor cannot be lighted.
public class Solution {
public int solve(int[] A, int B) {
int n = A.length;
int i = 0;
int count = 0;
while(i < n) {
boolean isBulbLighted = false;
int lr = Math.max(i - B + 1, 0);
int rr = Math.min(i + B - 1, n - 1);
// 0, 0, 1, 0, 1, 0, 0, 1
for(int j = rr; j >= lr; j--) {
if(A[j] == 1) {
count++;
i = j;
i += B;
isBulbLighted = true;
break;
}
}
if(!isBulbLighted) {
return -1;
}
}
return count;
}
}
Bro, at first I was reluctant to watch a 19 minute video but the way you deliver the solution is absolute delight. The flow of the code and the explanation were in sync.
This is the best explanation for this question. Great job!
Mam plz aap continue rakhiye ye series, views ko dhyan mat dijiye
Aapke channel bhut precious h
Heere ho har koi tarash nhi sakta
though the video was bit long , but it was worth watching it!! so nicely explained every bit of the line of code
Very nicely explained, thank you!
Great explanation, thanks so much!
Good explanation! Thanks for helping out 🤗
Thanks for the video!
Thanks for the explanation 😊
Nicely explained. Very easy to understand
Wow !!!!! Really a good explanations.
Very nicely explained...Thanks
Thank you ,that was nice application
int Solution::solve(vector &A, int B) {
int count =0;
int i=0;
int n=A.size();
while(i=left){
if(A[right]==1){
found=true;
break;
}
right--;
}
if(found==false){
return -1;
}
count++;
i=right+B;
}
return count;
} Correct code . i made a small correction i=right +B not right+B-1 as mentioned in the video.
quality of Explanation justifies your hard work !!
Great explanation
Fantastic explanation!! KUDOS
Great Explanation❤
MOST AWSOME CONTENT MAAM...
everytime I am stuck, you come up like magic. Thanks ma'm.
R u wall clock alwys stuck after putting battary u charged
What an awesome explanation!
Wow an awesome comment
nicely explained. !
such a good video
Most underrated channel
Nice explaination 😊
solving this question looks a piece of cake when explained by her!!!
Intuitive solution❤
very good explanation the tabs show how much u research for one question🙂
Can you please upload your code also? It will help us with revision purposes.
super..
best explanation!!
Glad you liked it
is Time complexity is O(n^2) ?
❤
int Solution::solve(vector &A, int B) {
int n = A.size();
int count = 0;
int i = 0;
bool bulbfound = false;
while(i=l){
if(A[r]==1){
count++;
i = B+r;
bulbfound = true;
break;
}
r--;
}
if(!bulbfound) return -1;
bulbfound = false;
}
return count;
}
i was just doing the mistake in the second while loop , btw nice explanation , but in the starting your voice was little crumbling , and have you made a git hub repo for interviewbit questions?
Wow thanks for the solution. It was an easy question how can't I do that. ;_;
can anyone tell me what will be the time complexity? Is it O(n^2)?
O(N).
The worst case : -
A = [0, 0, 0, 0], B = 1
We would have to iterate over every element..
can you please upload solution of Leetcode problem "127. Word Ladder"?
Surèeeeeeeeeeee dhanajoy i m redy for u
for java folks:
public static int solve(int[] arr, int k) {
if (k==0) return -1;
int i = 0, count = 0;
while (i < arr.length) {
int idx = lightItUp(arr, k, i);
if (idx == -1) return -1;
else {
i = idx + k;
count++;
}
}
return count;
}
public static int lightItUp(int arr[], int k, int i) {
int j = Math.min(i + k - 1, arr.length - 1);
while (j >= Math.max(i - k + 1, 0)) {
if (arr[j] == 1) {
return j;
}
j--;
}
return -1;
}
How much avg time did you take to solve questions?
How much u r taking less than that
Python Solution:
class Solution:
# @param A : list of integers
# @param B : integer
# @return an integer
def solve(self, A, B):
count = 0
i = 0
n = len(A)
while(i < n):
right = min(n-1, i + B - 1)
left = max(i - B + 1, 0)
bulbFound = False
while(right >= left):
if A[right] == 1:
bulbFound = True
break
right -= 1
if bulbFound == False:
return -1
else:
count += 1
i = right + B
return count
Make a tutorial on how to be focussed to see the main screen while watching your lectures.
Keep a mirror to the side where you can see your own reflection.
Idiots setting the corridor from starting index 1, while the array of lights starts from 0.
here is the one pass for starting index 0;
int i, end = -1, cnt = 0;
for (i = 0; i < A.size();)
{
if (A[i] == 1)
{
if (i - B + 1 > end + 1)
return -1;
end = i + B - 1;
i += i + B;
++cnt;
}
else
++i;
}
return cnt;
Nicely explained
thank you so much ma'am , I was not getting the problem I was afraid when I have read this problem need DP and backtracking concept and I have not yet studied it thank you so much for the confidante by your explanation I have got the problem