### eleganc's blog

By eleganc, history, 12 months ago,

Hi, I recently faced this problem in an OA. Any approaches to solve this?

An array consists of N elements. We want to minimize the absolute difference between adjacent elements of the array. We can change any integer to any other integer however at most K changes are allowed. If n <= 1 return 0.

Here is the exact problem link: https://www.codechef.com/CRK32020/problems/KEVIN?tab=statement There is some hint toward binary search, but I don't precisely infer how it is to be applied.

Constraints: 1 ≤ k ≤ n ≤ 2000 -1e9 ≤ Ai ≤ 1e9

Eg. N = 6, K = 3 Arr = [1 2 3 7 8 9] Here Arr can be transformed to [1 2 3 4 5 6] in 3 changes. And the answer becomes 1.

• +3

 » 12 months ago, # |   0 I think you must apply binary search by taking left as the minimum value of the absolute difference and right as the maximum. If an array exists with the minimum absolute value equal to the mid, then you must put right as mid (because we are finding the minimum difference). Otherwise left as mid.