Minimum Power

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
10 upvotes
Asked in company
Bloomreach

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'.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input-1
2
3 2
1 2 3
5 2
1 2 5 7 9
Sample Output-1
1
2
Explanation for Sample Input 1:
For test case 1:
    We blast the bomb of power ‘1’ at positions ‘1’ and ‘2’ and destroy all the enemy.
For test case 2:
    We blast the bomb of power ‘2’ at positions ‘7’ and ‘3’ and destroy all the enemies.
Sample Input -2
2
3 1
1 3 5
3 2
2 3 5
Sample Output -2
2
1
Hint

Can we destroy the enemies with the bomb of power ‘R’?

Approaches (2)
Brute Force

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.
Time Complexity

O(N * ceil((max(L) - min(L)) / 2)). Where ‘N’ is the number of the enemies, and ‘L’ is the list of the locations of the enemies.

We are iterating in the whole enemies list in each iteration. We are also sorting the array. Hence the complexity becomes O(NlogN + N * ceil((max(L) - min(L)) / 2)). Hence the overall complexity is O(N * ceil((max(L) - min(L)) / 2)).

Space Complexity

O(1).

We are creating four variables. Hence the overall complexity is O(1).

Code Solution
(100% EXP penalty)
Minimum Power
Full screen
Console