Minimize absolute difference between adjacent elements where atmost K changes allowed.

Revision en1, by eleganc, 2022-10-11 09:27:56

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: There is some hint toward binary search, but I don't precisely infer how it is to be applied.

Tags dynamic programming, binary search, ad hoc


  Rev. Lang. By When Δ Comment
en2 English eleganc 2022-10-11 09:30:53 179
en1 English eleganc 2022-10-11 09:27:56 578 Initial revision (published)