Question

Microsoft | OA Coding Questions and Solutions | Set - 35 | 2022

Answer 1

You are given N building blocks each of which has a height H. weight W. You want to build a tower by stacking up blocks to reach a height of atleast K.

 

You should consider the strength for each block which indicates the maximum amount of total weight of the blocks that can be stacked above a while building the tower.

 

Given these constraints: you are required to find whether it is possible to construct a tower with a height of at least K. if it is possible to build the tower with a height of at least then find the maximum safety factor of the tower.

 

Note:

 

• You should return-1 if it is impossible to build a tower that satisfies the given constraints.
• The maximum safety factor of the tower is the amount of weight you can add to the top of the tower without exceeding any block's strength.

 

Input Format:
The first line of input contains a single integer N denoting the number of building blocks.
The next line of input contains a single integer K denoting the required height of the tower.
Each line i of the N subsequent lines (where 0 <=i<N) contains an integer describing Hi that denotes the height of block i.

 

Sample Input	Sample Output	Explanation
3 5 3 3 2 10 5 3 6 4 15	5	Place block 1 upon block 3.Max safety:5
4 10 9 3 5 4 8 3 5 4 1 5	-1	It is not possible to arrange them
4 10 9 3 5 4 4 3 5 4 1 5 10 5	2	Block 3 in the lowermost layer block in the 2nd lower layer block 2 in the top layer .Max safety =2