eleganc's blog

By eleganc, history, 12 months ago, In English

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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.