Question :
Given an array arr[] denoting heights of N towers and a positive integer K, you have to modify the height of each tower either by increasing or decreasing them by K only once. After modifying, height should be a non-negative integer. Find out what could be the possible minimum difference of the height of shortest and longest towers after you have modified each tower.
Example 1:
Input:
K = 2, N = 4
Arr[] = {1, 5, 8, 10}
Output:
5
Explanation:
The array can be modified as
{3, 3, 6, 8}. The difference between
the largest and the smallest is 8-3 = 5.
Logic:
- Naive Approach O(n logn):
- The idea is to sort all elements increasing order. And for all elements check if subtract(element-k) and add(element+k) makes any changes or not.
- Below is the implementation of the above approach:
- Sort the given array
- after sorting declare 3 variables namely
- ans = last element - first element
- small = first element + k
- big = last element - k
- place pointer on second element and subtrack = arr [ i ] - k and then add = arr [ i ] + k
- if add < big do nothing
- if subtrack > small do nothing
- at last return min ( ans, big-small)
import java.util.*;
public class Solution{
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int k = sc.nextInt();
int n = sc.nextInt();
int arr[] = new int[n];
for(int i = 0; i < arr.length; i++){
arr[i] = sc.nextInt();
}
if (n == 1)
return;
// Sort all elements
Arrays.sort(arr);
// Initialize result
int ans = arr[n-1] - arr[0];
// Handle corner elements
int small = arr[0] + k;
int big = arr[n-1] - k;
int temp = 0;
if (small > big)
{
temp = small;
small = big;
big = temp;
}
// Traverse middle elements
for (int i = 1; i < n-1; i ++)
{
int subtract = arr[i] - k;
int add = arr[i] + k;
// If both subtraction and addition
// do not change diff
if (subtract >= small || add <= big)
continue;
// Either subtraction causes a smaller
// number or addition causes a greater
// number. Update small or big using
// greedy approach (If big - subtract
// causes smaller diff, update small
// Else update big)
if (big - subtract <= add - small)
small = subtract;
else
big = add;
}
System.out.println("Answer is: " + Math.min(ans, big - small));
}
}
Top comments (0)