Can Place Books

Easy

0/40

Average time to solve is 15m

Contributed by

5 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
6 2
0 0 0 0 0 1
7 2
1 0 1 0 1 0 1

Sample Output 1:

1
0

Explanation For Sample Input 1:

In the first test case, there are 6 slots in the almirah and you have bought 2 books from the market. One of the possible combinations is that you can keep book 1 at index 0, book 2 at index 2. So, 1 is the answer.

In the second test case, there are 7 slots in the almirah and you have bought 2 books from the market. But the slots which are empty already have books adjacent to them. You can’t keep any book in the almirah. So, 0 is the answer.

Sample Input 2:

2
2 2
1 0
8 3
0 0 0 0 0 0 0 0

Sample Output 2:

0
1

Explanation For Sample Input 2:

In the first test case, there are no slots in the almirah and you have bought 2 books from the market. But the slots which are empty already have books adjacent to them. You can’t keep any book in the almirah. So, 0 is the answer.

In the second test case, there are 4 slots in the almirah and you have bought 3 books from the market. So, 1 is the answer.

Hint 1

Can you count the number of slots available to put books?

Approaches (1)

Approach 1

Brute Force

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.

Time Complexity

O(N), where N is the number of elements in the array ‘arr’.

As we are having a loop for traversing the array ‘arr’. Hence the time complexity is O(N).

Space Complexity

O(1), as we are using constant extra space.

(100% EXP penalty)

Can Place Books

Console