Can anybody help solving this?

help
1

There are N positive numbers in an array present is strictly non-decreasing order.
The difference diff is defined as the maximum difference between the two adjacent elements of the array as
diff = max( arr[i+1] - arr[i] ) for 1<= i <= N-1.

You need to minimize the diff by removing exactly K elements.
Note : The first and last elements of the array are fixed (You cannot remove them).

Input Format :
The first line contains a single integer N.
The second line contains N space-separated integers.
The third line contains a single integer K.

Output Format :
Print a the minimized diff value.

Constraints :
3 <= N <= 10^5
1 <= K <= N-2
1 <= arr[i] <= 10^9

Time Limit : 1 Sec

Sample Case :
5
1 2 3 7 8
2

Sample Output :
5

Explanation :
There are 3 ways to remove K elements as (1,7,8) (1,3,8) and (1,2,8).
Diff values for the above cases will be 6 (7-1), 5 (8-3) and 6 (8-2).
Therefore the minimum value is 5

2

// k, a = arr
for(int i =0; i<= k; i++){
int maxDiff = INT_MIN;
for(int j =0; j < n-k-1; j++){
for(int y =0; y<= i + j; y++){
maxDiff = max(maxDiff, a[y+1] - a[y]);
}
}
minDiff = min(minDiff, maxDiff);
}

4

@rohits17 Can you please explain the approach??

5
6

@tamo11 I did go through that article. The main constraint here is the first and last elements of the arrays are fixed ie. we cannot remove them. I am not able to figure out how to implement that using this approach

7

Could you provide the link to the question?

8

@preyram I was asked this question in a test that I gave about a month ago

9

You can binary search for every value of diff and then check if this value can be achieved by removing k elements.

10

how to check for a particular mid value…that it satisifies the property of reducing k elements

11

Keep deleting numbers as long as the difference does not exceed mid(diff). If you can achieve the required mid by deleting more than k numbers, then you can do it using exactly k numbers.