Question 7

N number of balloons are kept at different heights. You are asked to find out number of arrows to burst them. When an arrow hits the balloon it goes one level down.

Assume that the balloons are having same size.

for example given the balloons heights as array(Array will be given in decreasing order of size) :

5 4 3 3 2 2 1 1 1

minimum number of arrows to shoot them is: 3

explanation:

using first arrow shoot: 5 4 3 2 1

using second arrow shoot: 3 2 1

using third arrow shoot: 1

Example 2:

5 4 2 1

minimum number of arrows to shoot them is: 2

using first arrow shoot: 5 4

using second arrow shoot: 2 1

Expecting the solution to be in O(1) space complexity.