any hints for this problem ?
k_torke
Try writing distance of 3 numbers in a,b,c format...
well, do you need to check all possibilities for k = 3 and n = 4 ???
let's see this example: a < b < c < d ...
try to see what possibilities you have to check and what not ...
let's see this example: a < b < c < d ...
try to see what possibilities you have to check and what not ...
for 3 numbers, its apparently abs(2*a - 2*c).
I need to check N - k+ 1 times, but then checking must be done in like O(1) or sth, which sounds impossible. I guess I'm missing sth.
I need to check N - k+ 1 times, but then checking must be done in like O(1) or sth, which sounds impossible. I guess I'm missing sth.
yes you need to check n-k+1 times ...
so you need to do checking in O(1) ...
and why is it imposible ???
Well first you need to notice that sulution will be k consecutive elements in sorted array ... what you noticed I guess because you said you need to check N-k+1 times.
and then you need to check all k consecutive elements ...
let's say you are on i-th element ...
then absolute value of all pairs with i-th elements is abs( (k-1)*a[i] - SUM((i-k),i-1) ) ...
because abs(a[i] - a[i-k])+abs(a[i] - a[i-k+1])+...+abs(a[i]-a[i-1]) = abs( (k-1)*i - SUM((i-k),i-1) ) ... all numbers are positive ...
so think how to do result for interval (i-k,i) if you have result for interval (i-k-1,i-1) ...
so you need to do checking in O(1) ...
and why is it imposible ???
Well first you need to notice that sulution will be k consecutive elements in sorted array ... what you noticed I guess because you said you need to check N-k+1 times.
and then you need to check all k consecutive elements ...
let's say you are on i-th element ...
then absolute value of all pairs with i-th elements is abs( (k-1)*a[i] - SUM((i-k),i-1) ) ...
because abs(a[i] - a[i-k])+abs(a[i] - a[i-k+1])+...+abs(a[i]-a[i-1]) = abs( (k-1)*i - SUM((i-k),i-1) ) ... all numbers are positive ...
so think how to do result for interval (i-k,i) if you have result for interval (i-k-1,i-1) ...
and use a fast sort:D