Min abs difference of K points in an array.

Revision en7, by Diksha_goyal, 2021-11-05 13:27:31

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)