Last Updated: 23 Dec, 2021

Minimum Power

Moderate

Asked in company

Problem statement

The new year is here, and the lockdown is also over. To celebrate your new year eve, you reach your friend's house. Your friend knows you love video games, so he made you a game as a present. In the game, you have ‘N’ enemies located at distinct positive integers points on the number line. You have an array ‘L’ of length ‘N’, where ‘L[i]’ represents the position of the ‘ith’ enemy.

You also have ‘K’ bombs each of power ‘R’. When you blast a bomb of power ‘R’ at position ‘i’, it will destroy everything within a range [i - R, i + R]. To win the game, you have to find the minimum value of ‘R’, such that it is possible to destroy every enemy. It is not necessary to use all ‘K’ bombs.

For example:

Let’s say the array ‘L’ = [1, 3, 4, 5] and 'K' = 2 then after bombing at position ‘2’ with a bomb of power ‘1’, enemies in the range [1, 3] will be destroyed. So the remaining enemy will be at position [4, 5]. These two can be bombed by placing another bomb at position '4'. Hence, the power is '1'.

Input Format-

First-line contains ‘T’, denoting the number of Test cases.
For each Test case:
The first line contains two space-separated integers, ‘N’ and ‘K’, denoting the number of enemies and number of bombs you have.
The following line contains an array ‘L’ of ‘N’ space-separated distinct positive integers representing the enemy’s location.

Output Format-

For each test case, you have to print a non-negative integer denoting the minimum power of the bomb, such that it is possible to destroy every enemy.

Note :

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints -

1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^5 
1 <= ‘K’ <= 1000
1 <= L[i] <= 10^9, for 1 <= i <= ‘N’
Note- Sum of ‘N’ over all test cases does not exceed 10^5.

Time Limit: 1 sec

Approaches

01 Approach

Approach: We will iterate for the value of ‘R’ in the range [0, ceil((max(L) - min(L)) / 2)]. We will greedily try to destroy the enemies for some power ‘R’. If we bomb at position ‘i’, all the enemies in the range [i - R, i + R] will be destroyed. It can also be interpreted as destroying a range of 2 * R + 1. We will sort the enemies position. Once we see an enemy that is not destroyed, we will destroy all the enemy in the range [i, i + 2 * R], where ‘i’ is the enemy's position that is not destroyed.

Algorithm:

Sort ‘L’.
Create three variables, ‘i’, ‘tot’, ‘next’.
Iterate using a for loop from r = 0 to ceil((max(L) - min(L)) / 2).
Update ‘tot’ to 0.
Update ‘i’ to 0.
While ‘tot’ < ‘K’ and i < ‘N’.
Update ‘next’ to L[i] + 2 * r.
Increment ‘tot’ by 1.
While i < ‘N’ and L[i] <= next.
Increment ‘i’ by 1.
If ‘i’ >= ‘N’.
Print ‘r’.
Break.

02 Approach

Approach: We will do the binary search on the minimum power of the bomb. We will greedily try to destroy the enemies for some power ‘R’. If we bomb at position ‘i’, all the enemies in the range [i - R, i + R] will be destroyed. It can also be interpreted as destroying a range of 2 * R + 1. We will sort the enemies position. Once we see an enemy that is not destroyed, we will destroy all the enemy in the range [i, i + 2 * R], where ‘i’ is the enemy's position that is not destroyed.

Algorithm:

Sort ‘L’.
Create two variables, ‘low’, ‘high’, and initialize them to ‘0’ and ceil((max(L) - min(L)) / 2), respectively.
Create four variables, ‘mid’, ‘tot’, ‘i’, ‘next’.
While ‘low’ < ‘high’.
Update ‘mid’ to (low + high) / 2.
Update ‘tot’ to 0.
Update ‘i’ to 0.
While ‘tot’ < ‘K’ and i < ‘N’.
Update ‘next’ to L[i] + 2 * mid.
Increment ‘tot’ by 1.
While i < ‘N’ and L[i] <= next.
Increment ‘i’ by 1.
If ‘i’ < ‘N’.
Update ‘low’ to ‘mid + 1’.
Else.
Update ‘high’ to ‘mid’.
Print ‘low’.

Similar problems

Element Count in Ranges

Posted: 9 Oct, 2025

First Digit One

Posted: 14 Oct, 2025

Minimize Maximum Adjacent Distance

Posted: 3 Nov, 2025

Sorted Doubly Linked List to Balanced BST

Posted: 3 Nov, 2025

Minimized Maximum of Products Distributed to Any Store

Posted: 22 Feb, 2026