Last Updated: 7 Apr, 2021

Ninja island

Moderate

Asked in companies

Solve now

Problem statement

There is a very famous ninja island having 2 * ‘N’ houses. On this island, the houses are built in such a way that they form a 2 * ‘N’ grid, where each cell in the grid represents a house. Some of the houses are occupied by ninjas, and the remaining houses are occupied by ordinary people. The king of this island wants to know the houses which are occupied by ninjas. The only thing he knows is that, out of ‘N’ houses, ‘K1’ and ‘K2’ houses are being occupied by ninjas in the first and second row, respectively. The king recently discovered that ‘ARR[i]’ houses are occupied by ninjas in the i-th column, where ‘i’ is from 0 to ‘N’ - 1. As the king is busy with the queen, he asked you to find the houses occupied by ninjas.

Input Format

The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains a single integer, ‘N’, where ‘N’ denotes the number of houses in a single row in ninja island.

The second line of each test case contains two space-separated integers, ‘K1’ and ‘K2’, where ‘K1’ and ‘K2’ denote the number of houses occupied by ninjas in the first and second row, respectively.

The third line of each test case contains ‘N’ space-separated integers, representing the number of houses occupied by ninjas in each of the ‘N’ columns.

Output Format:

For each test case, print a single line containing “1” if you have returned the correct 2 * ‘N’ binary grid, where 0 and 1 in the grid represent that the house is occupied by ordinary people and ninjas, respectively, else the output will be “0”.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 5000
0 <= K1, K2 <= N
0 <= ARR[ i ] <= 2

Where ‘T’ is the number of test cases,  ‘N’ denotes the number of houses in a single row in ninja island,  ‘K1’ and ‘K2’ denote the number of houses occupied by ninjas in the first and second row of the grid, respectively, and ‘ARR[i]’ denotes the number of houses occupied by ninjas in the i-th column.

Time limit: 1 sec.

Solve now

Approaches

01 Approach

The idea here is to iterate through all the ‘N’ columns from left to right and greedily assign houses to ninjas. For all the columns where two houses are occupied by ninjas, we can directly assign both the houses to ninjas. Similarly, for all the columns where 0 houses are occupied by ninjas, we assign both houses to ordinary people. Now, for all the columns where one house is occupied by ninjas, we assign a house in the first row if the number of remaining houses occupied by ninjas in the first row is greater than the number of remaining houses occupied by ninjas in the second row. Otherwise, we assign a house in the second row.

Algorithm:

Declare a 2 - Dimensional array, say ‘answer’ of size 2 * ‘N’, to store the required binary grid.
Initially assign all the 2 * ‘N’ houses to ordinary people.
Run a loop for ‘i’ from 0 to ‘N’ - 1.
- If the number of houses occupied by ninjas in the i-th column is 2.
  - Assign both the houses to ninjas, i.e., do ‘answer[0][i]’ = 1 and ‘answer[1][i]’ = 1.
  - Decrement ‘K1’ and ‘K2’ as we have assigned one house in both the first and second row, respectively.
Run a loop for ‘i’ from 0 to ‘N’ - 1.
- If the number of houses occupied by ninjas in the i-th column is 1:
  - If the number of remaining houses occupied by ninjas in the first row is greater than the number of remaining houses occupied by ninjas in the second row, i.e., if ‘K1’ is greater than ‘K2’.
    - Assign the house in the first row, i.e., do ‘answer[0][i]’ = 1.
    - Decrement ‘K1’ as we have assigned a house in the first row.
  - Else:
    - Assign the house in the second row, i.e., do ‘answer[1][i]’ = 1.
    - Decrement ‘K2’ as we have assigned a house in the second row.
If ‘K1’ is not equal to 0 or ‘K2’ is not equal to 0.
- This means there is no valid solution
- Return an empty grid.
Return ‘answer’.

Solve now