Equalize the array

Question

Challenge

You are given an array \$a\$ of integers. With a move you can increase or decrease an element of the array by 1. Your task is to equalize the array, that is make all the elements of the array equal by performing some moves. But that's not enough! You also want to make as few moves as possible.

Input

• A non-empty array \$a\$ of integers
• Optionally, the length of \$a\$.

Output

• The minimum number of moves needed to equalize the array \$a\$.

Rules

• Standard rules for valid submissions, I/O, loopholes apply.
• This is code-golf, so shortest solution (in bytes) wins. As usual, don't let ridiculously short solutions in golfy languages discourage you from posting a longer answer in your language of choice.
• This is not a rule, but your answer will be better received if it includes a link to test the solution and an explanation of how it works.

Examples

Input --> Output
[10] --> 0
[-1, 0, 1] --> 2
[4, 7] --> 3
[6, 2, 3, 8] --> 9
[5, 8, 12, 3, 2, 8, 4, 5] --> 19
[1,10,100] --> 99

Answer 1

Wolfram Language (Mathematica), 19 bytes

Tr@Abs[#-Median@#]&

Try it online!

For 1D integer array, Tr works the same way as Total.

How?

Simple application of triangle inequality.

...

I originally intended to write the proof here, but then decide to look up https://math.stackexchange.com instead and found The Median Minimizes the Sum of Absolute Deviations (The \$ {L}_{1} \$ Norm).

By knowing the name of the operator, this is an alternative 19-byte solution:

Norm[#-Median@#,1]&

• user202729: Random comment: Median is a bit too hard for some esoteric languages.
• user202729: Looking around a bit, the only submission in esoteric language in the "compute the median" challenge is WW's Brain-Flak one.

Answer 2

JavaScript (Node.js), (削除) 50 (削除ここまで) 48 bytes

Saved 2 bytes thanks to Arnauld

a=>a.sort((x,y)=>x-y,r=0).map(n=>r+=a.pop()-n)|r

Try it online!

Sort the array ascending then sum:

 a[last] -a[0] // moves to equalise this pair
+ a[last-1] -a[1] // + moves to equalise this pair
+ ...etc

• Arnauld: Nice one! You can save 2 bytes with a=>a.sort((x,y)=>x-y).map(n=>r+=a.pop()-n,r=0)|r.

Answer 3

Perl 6, (削除) 29 (削除ここまで) 28 bytes

-1 byte thanks to nwellnhof

{sum (.sort[*/2]X-$_)>>.abs}

Try it online!

Explanation

{ } # Anonymous code block
 .sort[*/2] # Get the median of the input array
 X-$_ # Subtract all elements from the median
 ( )>>.abs # Get the absolute of each value
 sum # Sum the values

• nwellnhof: You can swap the X- operands to save a byte.

Answer 4

05AB1E, 4 bytes

ÅmαO

Try it online!

Explanation

Åm # push median of input
 α # absolute difference with each in input
 O # sum

• Magic Octopus Urn: Median! That's the word I was looking for! ZL€αOW was my attempt ._.

Answer 5

Japt -g, (削除) 7 (削除ここまで) 6 bytes

£xaXÃÍ

Try it

£xaXÃÍ :Implicit input of array U
£ :Map each X
 x : Reduce by U by addition after applying
 aX : Absolute difference with X
 Ã :End map
 Í :Sort
 :Implicit output of first element

Answer 6

JavaScript (ES6), (削除) 60 (削除ここまで) (削除) 56 (削除ここまで) 55 bytes

Saved 1 byte thanks to @Shaggy

a=>a.map(r=k=>r=a.map(n=>m+=n>k?n-k:k-n,m=0)|m>r?r:m)|r

Try it online!

How?

Unless there's some trick that I'm missing, computing the median in JS turns out to be longer. Probably around 65 bytes because of the required callback for sort() to circumvent the default lexicographical sort and the rather lengthy Math.abs():

a=>a.sort((a,b)=>b-a).map(n=>s+=Math.abs(n-a[a.length>>1]),s=0)|s

Instead of that, we try all values in the original array as the equalizing value.

• Shaggy: -2 bytes by declaring r within the first map.

Answer 7

Haskell, 34 bytes

f l=minimum[sum$abs.(m-)<$>l|m<-l]

Try it online!

Finds the total distance of all elements to the median, testing each element in the list as the potential median and taking the smallest result.

Answer 8

Jelly, 4 bytes

ạÆṁS

Try it online!

How it works

ạÆṁS – Full program. Takes an array A of integers as input from argument 1.
 Æṁ – Median. For odd-length A, middle element of S. For even-length A, the
 arithmetic mean of the two middle elements of S. Where S = A sorted.
ạ – Absolute difference of each element with the median.
 S – Sum.

Answer 9

Python 2, 46 bytes

lambda l,n:sum(l[-~n/2:l.sort()])-sum(l[:n/2])

Try it online!

Takes the list length n as an argument. Computes the top-half sum minus the bottom-half sum by slicing the sorted list into the first n/2 and last n/2 elements.

The expression l[-~n/2:l.sort()] is equivalent to computing l.sort(), which modifies the list in place, then doing l[-~n/2:None], where the list slicing ignores upper bound of None that l.sort() produced. It might seem like the list was sorted too late to be sliced right, but Python seems to evaluate the slice arguments before "locking in" the list to be sliced.

---

Python 2, 47 bytes

lambda l,n:sum(abs(x-sorted(l)[n/2])for x in l)

Try it online!

The boring method of summing the distance of each value from the median. Takes the length n as an argument.

---

Python, 51 bytes

f=lambda l:l>l[l.sort():1]and l[-1]-l[0]+f(l[1:-1])

Try it online!

Sorts the list in place, then repeatedly adds the last (highest remaining) entry minus the first (lowest remaining) entry, and recurses on the list without these elements until only 0 or 1 remain. Usings pop's gets the same length: l.pop()-l.pop(0)+f(l).

The l.sort() is stuck in a place where the None it returns has no effect. The slice l[None:1] is the same as l[:1] because Nones in slices are ignored.

---

Python, 54 bytes

lambda l:sum(l.pop()-l.pop(0)for _ in l[1:l.sort():2])

Try it online!

A cute list comprehension that ignores the argument iterated over and modifies the list in place by repeatedly popping the first and last elements. We ensure that the list comprehension is done len(l)//2 times by iterating over every other element of l skipping the first, done with l[1::2]. The l.sort() producing None can be stuck in the unused slice end argument.

• S.S. Anne: Does Python have /=? If so, I may see a way to save a byte.
• xnor: @S.S.Anne Yes, Python has !=. Excited to see what you came up with!
• S.S. Anne: I said /=, not !=.
• S.S. Anne: lambda l,n:sum(l[-~n/=2:l.sort()])-sum(l[:n])? I don't know Python but the /= trick is pretty much equivalent to what I'd do with C.
• xnor: Oh, I though you meant like /= in Haskell! Yes, Python has /= to do like a/=2 for a=a/2, but beware that Python doesn't allow statements (which a/=2 is) within lambdas.

Answer 10

APL(Dyalog), 12 bytes

{⌊/+/|⍵∘.-⍵}

Brute forces by testing each number as the equalizer. Not sure if tacit is shorter, but I can't figure it out.

TIO

Answer 11

TI-Basic, (削除) 18 (削除ここまで) 6 bytes

sum(abs(Ans-median(Ans

-12 bytes from Misha Lavrov (I haven't used TI-Basic in a while and I forgot it's lists can do that)

TI-Basic is a tokenized language. All tokens used in this answer are one byte.

Takes input as {1,2,3,4}:prgmNAME

Basically the same idea as most other answers: subtract through by the median, then take the sum.

Explanation:

sum(abs(Ans-median(Ans
sum( # 1 byte, Add up:
 abs( # 1 byte, the absolute values of
 Ans-median(Ans # 4 bytes, the differences between each element and the list's median

• Misha Lavrov: sum(abs(Ans-median(Ans also works. (And "TI-84 Plus CE" seems overly specific; this will work at least on any 83-series calculator, and probably also the 73 and 82.)

Answer 12

Röda, 33 bytes

{|a|a|abs _-[sort(a)][#a//2]|sum}

Try it online!

Explanation:

{|a| /* Anonymous function with parameter a */
 a| /* Push items in a to the stream */
 /* For each _ in the stream: */
 abs /* Abstract value of */\
 _- /* the value from stream minus */\
 [sort(a)][ /* the value in the sorted version of a at index */
 #a//2 /* length of a / 2 (the median) */
 ]|
 sum /* Sum of all values in the stream */
}

Answer 13

C (gcc), (削除) 100 (削除ここまで) 93 bytes

e(q,u,a,l,i,z)int*q;{i=1<<31-1;for(a=u;a--;i=z<i?z:i)for(l=z=0;l<u;)z+=abs(q[l++]-q[a]);q=i;}

Brute-force solution, tries to equalize with each element. Try it online here.

Thanks to ceilingcat for golfing 7 bytes.

Ungolfed:

e(q, u, a, l, i, z) int *q; { // function taking an array of int and its length; returns an int (extra parameters are variables and don't have to be passed when calling e())
 i = 1 << 31 - 1; // construt the maximum value of a signed 4-byte integer
 for(a = u; a--; i = z < i ? z : i) // loop through the array, testing each element as the equalizer; if the number of moves is smaller than the current minimum, set it as the new minimum
 for(l = z = 0; l < u; ) // loop through the array ...
 z += abs(q[l++] - q[a]); // ... and sum the number of moves it takes to equalize each element
 q = i; // return the minimum number of moves
}

• S.S. Anne: ~0/2-1 instead of 1<<31/1 might save a byte.
• Jonathan Frech: You could replace q with E.
• Jonathan Frech: I think << has lower precedence than - (source: en.cppreference.com/w/c/language/operator_precedence), leading to 1<<31-1 being parsed as 1<<(31-1) which is 1<<30.

Answer 14

R, 29 bytes

sum(abs(median(a<-scan())-a))

Try it online!

Answer 15

PHP, 69 bytes

function($a,$c){for(sort($a);$c-->$d;)$s+=$a[$c]-$a[+$d++];return$s;}

anonymous function. Try it online.

Answer 16

Ruby, 38 bytes

->a{a.map{|x|a.sum{|y|(y-x).abs}}.min}

Try it online!

Answer 17

Java 8, 116 bytes

With java.util.List<Integer> as parameter, which has a short sort-builtin, but is longer to retrieve a value at a given index:

L->{L.sort(null);int r=0,l=L.size(),k=l;for(;k-->0;)r+=Math.abs(L.get(k)-(L.get(l/2+~l%2)+L.get(l/2)>>1));return r;}

Try it online.

With int[] (integer-array) as parameter, which has a long sort-builtin, but is shorter to retrieve a value at a given index:

a->{java.util.Arrays.sort(a);int r=0,l=a.length,k=l;for(;k-->0;)r+=Math.abs(a[k]-(a[l/2+~l%2]+a[l/2]>>1));return r;}

Try it online.

Code explanation (of the array answer):

a->{ // Method with integer-array as parameter and integer return-type
 java.util.Arrays.sort(a); // Sort the input-array
 int r=0, // Result-sum, starting at 0
 l=a.length, // The length of the input-array
 k=l;for(;k-->0;) // Loop `k` in the range (length, 0]:
 r+= // Increase the result-sum by:
 Math.abs(a[k]- // The absolute difference of the `k`'th value of the array,
 (a[l/2+~l%2]+a[l/2]>>1)); // and the median of the array
 return r;} // And then return this result-sum

General explanation:

1. Sorts the input-list
2. Calculate the \$median\$
3. Calculate the absolute difference of each value with this \$median\$
4. Sum those

The median of the array \$a\$ is calculated by:
1) Taking the sorted values at the (0-based) indices \$i\$ and \$j\$, which are calculated like this (using the l/2+~l%2 instead of l/2-(l+1)%2 trick to save bytes):
\$j=\left\lfloor\frac{1/2}l\right\rfloor\$
\$i=\left\lfloor\frac{1/2}l\right\rfloor - ((l+1) \bmod 2)\$
Note that \$i=j\$ for odd-sized arrays.

2) And then adding these together, and integer-dividing them by 2 (using the i+j>>1 instead of (i+j)/2 trick to save bytes):
\$median = \left\lfloor\frac{a[i]+a[j]}{2}\right\rfloor\$

After which we can use this \$median\$ to calculate the absolute difference with the current item, which we can use to calculate the total sum:
\$\sum\limits_{k=0}^{l} = \left\lvert a[k] - median\right\rvert\$
with \$l\$ being the length of the array \$a\$, and \$k\$ being the (0-based) index.

• S.S. Anne: I think you can set k to l/2 and then iterate over l to save a few bytes. And the >0 is also most likely not needed.
• Kevin Cruijssen: @S.S.Anne Unfortunately I also need l for the l%2 part, otherwise the first part of your comment would have been a good suggestion. As for removing >0, that isn't possible in Java. Unlike C, Python, JavaScript, and such (where 0 is a valid falsey alternative and any other integer a valid truthy alternative), Java's booleans (true/false) are strongly typed.

Answer 18

05AB1E, 4 bytes

δαOß

I know there is already an existing 4-bytes 05AB1E answer using the median builtin Åm, but I decided to post this alternative 4-byter without this builtin.

Try it online or verify all test cases.

Explanation:

δ # Apply the following command double-vectorized on the given two arguments,
 # which will use the input-list twice implicitly, since the stack is empty:
 α # Absolute difference
 # i.e. [1,10,100] → [[0,9,99],[9,0,90],[99,90,0]]
 O # Sum each of these inner lists
 # → [108,99,189]
 ß # Pop and push the minimum of this list
 # → 99
 # (after which this is output implicitly as result)

Answer 19

Attache, 18 bytes

Sum##Abs@`-#Median

Try it online!

Explanation

Sum##Abs@`-#Median
 Median take the median of the input list
 Abs@`-# absolute difference with the original list
Sum## sum of all elements

Answer 20

J, 15 bytes

[:<./1#.|@-/~"{

Essentially the same as Shaggy's Japt solution.

Try it online!

How it works?

|@-/~"{ - creates a table /~ of absolute differences |@- of each number to all others "{

 |@-/~"{ 6 2 3 8
0 4 3 2
4 0 1 6
3 1 0 5
2 6 5 0

1#. sums each row

 1#.|@-/~"{ 6 2 3 8
9 11 9 13

[:<./ finds the smallest item (reduce by minimum)

 ([:<./1#.|@-/~"{) 6 2 3 8
9

• Bubbler: "{ can be simply removed.

Answer 21

Charcoal, (削除) 16 (削除ここまで) 11 bytes

I⌊EθΣEθ↔−ιλ

Try it online! Link is to verbose version of code. Edit: Saved 5 bytes thanks to @Arnauld. Explanation:

 Eθ Map over input array
 Eθ Map over input array
 ι Outer value
 λ Inner value
 − Difference
 ↔ Absolute value
 Σ Sum
 ⌊ Minimum
I Cast to string
 Implicitly print

• Arnauld: This should work for 11 bytes.
• Neil: @Arnauld Ah, of course, for odd length arrays the median is always a member of the array, and for even length arrays, the sum is the same for all the values between and including the middle two. Thanks!

Answer 22

Visual C#, 138 bytes

int s=0;foreach(string i in a)s+=int.Parse(i);int x=s/a.Length;int o=0;foreach(string i in a)o+=Math.Abs(int.Parse(i)-x);Console.Write(o);

ungolfed:

int s = 0; // Takes a string array of arguments a as input
foreach (string i in a) 
 s += int.Parse(i); // s as sum of the array elements
int x = s / a.Length; // calculating the target value of all elements
int o = 0; // o as minimum number of moves
foreach (string i in a)
 o += Math.Abs(int.Parse(i) - x); // summing up the moves to the target value
Console.Write(o);

Try it online!

• Meerkat: This code is failing on TIO for [1,10,100]. It's returning 126 instead of 99.

Answer 23

PHP, 78 bytes

Sorts the array, then loop through a copy, popping elements off the original and summing the absolute difference, that needs to be halved for the return.

function m($n){sort($n);foreach($n as$i)$r+=abs(array_pop($n)-$i);return$r/2;}
var_dump(
 m([10]),
 m([-1, 0, 1]),
 m([4, 7]),
 m([6, 2, 3, 8]),
 m([5, 8, 12, 3, 2, 8, 4, 5]),
 m([1,10,100])
);

Output:

int(0)
int(2)
int(3)
int(9)
int(19)
int(99)

Answer 24

C++ (gcc), 94 bytes

#import<regex>
int f(int c,int*a){int s=0,d=0;for(std::sort(a,a+c);c-->d;)s+=a[c]-a[d++];c=s;}

Port of the PHP solution. Kudos to Titus!

Input size of the array and a non-const mutable array. Output the minimum number of moves required to equalize the array.

-4 bytes thanks to ceilingcat!

Try it online!

Answer 25

V (vim), 84 bytes

:sort
Go<c-r>=(line('$')-1)/2
<esc>dd@"kk0vg_"ayGqq0C<c-r>=abs(<c-r>"-<c-r>a)
<esc>k@qq@q:%s/\n/+
$x0C<c-r>=<c-r>"
<esc>

Try it online!

<c-r> is very helpful in finding the median and the whole calculation in general.

Answer 26

PowerShell, 52 bytes

($a=$args|sort)|%{$_-$a[--$i]}|%{$s-=$_*($_-lt0)}
$s

Try it online!

Answer 27

Perl 5 -ap, 39 bytes

map$\+=abs$_-(sort{$a-$b}@F)[@F/2],@F}{

Try it online!

Answer 28

PowerShell, 107 bytes

$f={param($i)$m=($i|sort)[[int](($i.count-1)/2)];($j+=$i.foreach({([math]::abs($m-$_))})|measure -sum).Sum}

Try it online!

PowerShell, 115 bytes

function f($i){$m=($i|sort)[[int](($i.Count-1)/2)];return($j+=$i.ForEach({([math]::Abs($m-$_))})|measure -Sum).Sum}

Try it online!

Answer 29

JavaScript (Node.js), 52 bytes

f=a=>(v=a.sort((x,y)=>x-y).pop()-a.shift())?v+f(a):0

Try it online!

Answer 30

Kotlin Android, 200 bytes

fun m(a:IntArray){var d=0;var s=0;var p=a.max()!!.times(a.size);var x =0;for(i in a.indices){x=a[i];d=0;s=0;while(d<a.size){if(x-a[d]<0)s=((x-a[d])*-1)+s;else s=((x-a[d]))+s;d++};if(p>s)p=s};print(p)}

Try Online

• Jo King: Note that input via a pre-declared variable is not allowed. Additionally, you can shorten your variable names a bit
• Syed Hamza Hassan: sure, i will do it shortly.
• S.S. Anne: You can do a=s=0 and -(x-a[d])+s, along with multiple other things.