Min abs difference of K points in an array.

Revision en2, by Diksha_goyal, 2021-11-05 12:55:28

Given an array ~~~~~ A ~~~~~

of size n i.e., ~~~~~ A = {A_1, A_2, ... A_n} ~~~~~

you are given ~~~~~ K ~~~~~

. you can choose any ~~~~~ K ~~~~~

integers (not necessarily from the given array)

i.e, X_1, X_2, X_3 .... X_K

Now, we define a function ~~~~~ F ~~~~~

for each A_i, such that ~~~~~ F_i = min(abs(A_i — X_j)) ~~~~~

 where 1<= j <=K.

find the minimum value of ~~~~~ F_1 + F_2 + .... F_n. ~~~~~

constraints:

1 <= n <= 10^5
1<= K <= n
Tags sorting, array, number theory, median, algorithms, optimization, maths

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English Diksha_goyal 2021-11-05 13:27:31 8 Tiny change: 'n(abs(A_i &mdash; X_j)) whe' -> 'n(abs(A_i - X_j)) whe'
en6 English Diksha_goyal 2021-11-05 12:57:20 36
en5 English Diksha_goyal 2021-11-05 12:56:27 20
en4 English Diksha_goyal 2021-11-05 12:56:08 0 Reverted to en1
en3 English Diksha_goyal 2021-11-05 12:55:47 196 Reverted to en1
en2 English Diksha_goyal 2021-11-05 12:55:28 196
en1 English Diksha_goyal 2021-11-05 12:53:37 424 Initial revision (published)