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.