There is a pond with fish in it divided into ‘N’ segments. Each segment can contain at most 1 fish. You plan to go fishing, and want to catch ‘K’ fish in one attempt. To catch fish, you can drop a net of any size (not exceeding the size of the pond) on a continuous segment of a pond and catch all the fish present in that segment.
You want to save the planet (Ironic, right?), and hence want to minimize the size of the net you use, so as to disturb as little of the ecosystem as possible.
For example:
If the pond has 5 segments as [1, 0, 1, 0, 1], with 1 representing a fish and 0 representing no fish, and if we need to catch 2 fish, we can either pick the range [1,3] or [3,5].
Note: It is NOT guaranteed that the pond contains at least K fish.
The first line contains 'T', denoting the number of test cases.
For each Test :
The first line contains two space-separated integers, ‘N’ and ‘K’.
The second line contains ‘N’ integers, each of them either 0 or 1, with 1 representing a fish and zero representing no fish.
For each case, print one integer, the minimum size of the net you need to use. If it is not possible to catch ‘K’ fish, print -1.
You are not required to print the expected output. It has already been taken care of. Just implement the function.
1 <= 'T' <= 10
2 <= 'N',’K’<= 10^5
A[i] <= {0,1}, i ∈ (1,N)
Note - The sum of 'N' over all test cases does not exceed 10^5.
Time Limit: 1 sec
2
8 3
1 0 1 1 0 0 1 1
5 2
1 0 0 0 0
4
-1
For test case 1:
Some of the ways to catch 3 fish are, [1,4], [3,7] and [4,8]. The net of size from index 1 to 4 is the smallest available, hence the answer is 4.
For test case 2:
The pond has only 1 fish, so it is impossible to catch 2 fish. Hence the answer is -1.
2
5 3
1 1 1 0 0
4 2
1 0 0 1
3
4
From each starting point, how large must the net be to catch ‘K’ fish?
Approach: From each point, we can consider that to be our starting point, and keep moving towards the right until either we get ‘K’ fish, or we reach the end of the array.
If we do manage to get ‘K’ fish, we can stop moving rightwards, and the size of the current segment is a viable answer.
The minimum of all such viable answers from all possible starting points will be our answer.
Algorithm:
O(N^2), where ‘N’ is the number of segments.
From each of the N points, we move rightwards as long as we don’t get ‘K’ fish, which is ‘N’ steps in the first case. Hence, the time complexity is O(N*N) = O(N^2)
O(1), as we don’t use any extra space in this approach.
All tags
Sort by
Interview problems
Python solution (using two pointer + sliding window approach)
def minimumNet(n, k, arr):
if(n == 1):
if(k == 1 and arr[0] == 1):
return 1
else:
return -1
if(arr.count(1)<k):
return -1
p = 0
q = p+1
c = 0
ans = float('inf')
if (arr[p] == 1):
c+=1
while q<n:
if(arr[q] == 1):
c+=1
if(c>=k):
while c>=k:
if(c == k):
ans = min(ans,q-p+1)
if(arr[p] == 1):
c-=1
p+=1
q+=1
return ans
Interview problems
Solution
#include <bits/stdc++.h>
int minimumNet(int n, int k, vector<bool> fish)
{
// Write your code here.
if(n==1 && k==1){
if(fish[0]){
return 1;
}else{
return -1;
}
}
int sum = 0;
for(int i=0;i<n;i++){
sum+=fish[i];
}
//not enough fish in the pond
if(sum<k){
return -1;
}
//cout<<sum<<endl;
//enough fish exists find the smallest segment that contains the fish
int s = 0;
int e = 1;
int ans = 0;
int min_ans = INT_MAX;
sum = fish[s];
while(e<n){
sum += fish[e];
if(sum == k){
if(k==1){
return 1;
}
ans = e-s;
if(ans<min_ans){
min_ans = ans;
}
s++;
sum = fish[s];
e = s + 1;
}else if(sum<k){
e++;
}
}
return min_ans+1;
}
Interview problems
O(n) | two-pointer approach
#include <bits/stdc++.h>
int minimumNet(int n, int k, vector<bool> fish)
{
// Write your code here.
int i=0, j=0, count = 0, minSize = n+1;
while(j < n){
if(fish[j] == 1){
count++;
}
while(count >= k){
minSize = min(minSize, j-i+1);
if(fish[i] == 1) count--;
i++;
}
j++;
}
return minSize == n+1 ? -1 : minSize;
}Interview problems
i got the answer with this approach
#include <bits/stdc++.h>
int minimumNet(int n, int k, vector<bool> fish)
{
int count = 0;
vector<int> netsize;
for(int i=0;i<n;i++){
if(fish[i]){
count++;
netsize.push_back(i);
}
}
if(count < k || n < k){
return -1;
}
int ans = INT_MAX;
for(int i = 0 ; i < netsize.size()-k+1; i++){
if(netsize[i+k-1] - netsize[i] + 1 < ans){
ans = netsize[i+k-1] - netsize[i] + 1;
}
}
return ans;
}
Interview problems
what's wrong in this logic
#include <bits/stdc++.h>
int minimumNet(int n, int k, vector<bool> fish)
{
// Write your code here.
int sum =0;
for(int i=1; i<=n; i++)
{
sum = sum + fish[i];
if(sum == k)
{
return i;
}
else
{
return -1;
}
}
}
Interview problems
POINTER APPRAOCH.
Brute force approach(avoid this but also try to implement this so you can understand the pointer approach)
POINTER APPROACH
#include <bits/stdc++.h>
int minimumNet(int n, int k, vector<bool> fish) { vector<int> index; for(int i=0 ; i<n ; i++){ if(fish[i]&1) index.push_back(i); } int size=index.size(); if(size<k) return -1; int i=0; int j=i+k-1; int ans=INT_MAX; while(j<size){ ans=min(index[j]-index[i]+1,ans); i++; j++; } return ans; }
Interview problems
Test Case Query
188 1
0 0 1 1 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 1 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1 0 0 1 1 1 ….
In this test case the expected output given is 3 but i am getting 1. But I think according to problem statement it should be 1 only. Please let me know if I am right or wrong.
Interview problems
Using binary search with time complexity of O(Nlog(N))
/*#include <bits/stdc++.h>
bool check( int mid,vector<bool> &fish,int k){
int count=0;
for(int i=0;i<mid;i++){
count+=fish[i];
}
if(count>=k)return 1;
int j=0;
for(int i=mid;i<fish.size();i++){
count-=fish[j];
count+=fish[i];
j++;
if(count>=k)return 1;
}
return 0;
}
int minimumNet(int n, int k, vector<bool> fish)
{
int low=1;
int high=n;
int ans=-1;
while(low<=high){
int mid=low+(high-low)/2;
if (check(mid,fish,k)) {
high = mid - 1;
ans=mid;
}
else low=mid+1;
}
return ans;
}*/
Interview problems
Logical error
#include <bits/stdc++.h>
int minimumNet(int n, int k, vector<bool> fish)
{
int count = 0;
for(int i=0;i<n;i++)
{
if(fish[i]==1) count++;
}
if(count<k) return -1;
else if(k==1 && count>=1) return 1;
count = 0;
int mini = INT_MAX;
for(int i=0;i<n-1;i++)
{
if(fish[i]==1)
{
count++;
for(int j=i+1;j<n;j++)
{
if(fish[j]==1)
{
count++;
if (count == k)
{
mini = min(mini, j - i + 1); //3-0 is actually 4 so, +1
//cout<<"mini="<<mini<<endl;
break;
}
//cout<<"ival= "<<i<<" if"<<endl;
}
//cout<<"for"<<endl;
}
}
else
{
//cout<<"ELSE"<<endl;
count = 0;
}
//cout<<"-------------------------------"<<endl;
}
return mini;
}
All the test cases are not getting passed?….What exactly is the error?
Interview problems
why this error in one testcase when i submit this code
Traceback (most recent call last): File "runner.py", line 37, in file = open(os.environ['EXEC_COUNTER_FILE'], "w") TypeError: an integer is required (got type str)
from os import *
from sys import *
from collections import *
from math import *
from typing import *
def minimumNet(n: int, k: int, fish: List[int]) -> int:
if n<k:
return -1
if sum(fish)<k:
return -1
if k==1 and sum(fish)!=0:
return 1
l=0
r=l+k-1
ans=n
while l<n and r<n:
if sum(fish[l:r+1])==k:
c=r-l+1
if c<ans:
ans=c
l+=1
else:
r+=1
return ans
