Last Updated: 8 Apr, 2021
Can Place Books
Easy
Asked in companies
You have an almirah in which books are kept. There are ‘N’ slots to keep books. Books are already present in some of the slots while some of the slots are empty. You have bought ‘K’ books from the market. You are supposed to place all ‘K’ books in the almirah under the condition that no two books should be kept adjacent. The slots of the almirah are given in the form of an array: 0 means the slot is empty and 1 means the slot is already filled with a book. Print 1 if you can keep all the books under the given condition and 0 otherwise.
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases. The test cases follow.
The first line contains two integers ‘N’ and ‘K’, which denotes the number of slots and the number of books that you bought from the market.
The second line contains 'N' integers denoting the elements of the array ‘ARR’.
Output Format:
For each test case, print 1 if all ‘K’ books can be kept under the given condition. 0 otherwise.
Print the output of each test case in a separate line.
Note:
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1<= T <= 50
1 <= N <= 10^4
1 <= K <= 10^4
1 <= ARR[i] <= 10^4
Where ’T’ is the number of test cases, N denotes the number of slots in the almirah, ‘K’ denotes the number of books that you bought from the market, ARR[i] denotes the element at index ‘i’.
Time Limit: 1 sec
Approaches
Approach: The idea is to traverse over the array and if the adjacent slots of the current slot are empty, then put a book in the current slot. If you can successfully keep k books then return 1.
The steps are as follows:
- Initialize two integers ‘SLOTSAVAILABLE’ to 0, and ‘n’ to the size of the given array ‘ARR’.
- Iterate from ‘i’ = 0 to ‘N’:
- If the current slot is empty and its adjacent slots are empty, then keep a book in that slot and increment ‘SLOTSAVAILABLE’ by 1.
- Return ‘1’ if the ‘SLOTSAVAILABLE’ is greater than or equal to k.
- If we come out of the loop, it means k is greater than ‘SLOTSAVAILABLE’. So, return 0.