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]&

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

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

Answer 4

05AB1E, 4 bytes

ÅmαO

Try it online!

Explanation

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

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.

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.

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

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
}

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

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.

Answer 17

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 18

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 19

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

Answer 20

Charcoal, 16 11 bytes

Ｉ⌊ＥθΣＥθ↔⁻ιλ

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

  Ｅθ        Map over input array
     Ｅθ     Map over input array
         ι  Outer value
          λ Inner value
        ⁻   Difference
       ↔    Absolute value
    Σ       Sum
 ⌊          Minimum
Ｉ           Cast to string
            Implicitly print

Answer 21

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!

Answer 22

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 23

Ruby, 38 bytes

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

Try it online!

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