28
\$\begingroup\$

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 , 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
\$\endgroup\$

29 Answers 29

9
\$\begingroup\$

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]&
\$\endgroup\$
  • \$\begingroup\$ Random comment: Median is a bit too hard for some esoteric languages. \$\endgroup\$ – user202729 Sep 29 '18 at 15:31
  • 1
    \$\begingroup\$ Looking around a bit, the only submission in esoteric language in the "compute the median" challenge is WW's Brain-Flak one. \$\endgroup\$ – user202729 Sep 29 '18 at 15:42
9
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice one! You can save 2 bytes with a=>a.sort((x,y)=>x-y).map(n=>r+=a.pop()-n,r=0)|r. \$\endgroup\$ – Arnauld Sep 29 '18 at 18:23
7
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ You can swap the X- operands to save a byte. \$\endgroup\$ – nwellnhof Sep 30 '18 at 11:30
6
\$\begingroup\$

05AB1E, 4 bytes

ÅmαO

Try it online!

Explanation

Åm     # push median of input
  α    # absolute difference with each in input
   O   # sum
\$\endgroup\$
  • \$\begingroup\$ Median! That's the word I was looking for! ZL€αOW was my attempt ._. \$\endgroup\$ – Magic Octopus Urn Nov 2 '18 at 13:26
6
\$\begingroup\$

Japt, 7 bytes

£xaXÃrm

Try it


Explanation

            :Implicit input of array U
£           :Map each X
  aX        :  Absolute difference between X and each element in U
 x          :  Reduce by addition
    Ã       :End map
     rm     :Reduce by minimum
\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ -2 bytes by declaring r within the first map. \$\endgroup\$ – Shaggy Sep 29 '18 at 16:24
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Does Python have /=? If so, I may see a way to save a byte. \$\endgroup\$ – S.S. Anne Feb 5 at 16:13
  • 1
    \$\begingroup\$ @S.S.Anne Yes, Python has !=. Excited to see what you came up with! \$\endgroup\$ – xnor Feb 5 at 22:41
  • \$\begingroup\$ I said /=, not !=. \$\endgroup\$ – S.S. Anne Feb 5 at 23:16
  • \$\begingroup\$ 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. \$\endgroup\$ – S.S. Anne Feb 5 at 23:16
  • \$\begingroup\$ 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. \$\endgroup\$ – xnor Feb 5 at 23:17
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ 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.) \$\endgroup\$ – Misha Lavrov Sep 30 '18 at 0:51
3
\$\begingroup\$

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 */
}
\$\endgroup\$
3
\$\begingroup\$

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
}
\$\endgroup\$
2
\$\begingroup\$

R, 29 bytes

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

Try it online!

\$\endgroup\$
2
\$\begingroup\$

PHP, 69 bytes

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

anonymous function. Try it online.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – S.S. Anne Feb 5 at 12:55
  • \$\begingroup\$ @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. \$\endgroup\$ – Kevin Cruijssen Feb 5 at 13:02
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ This should work for 11 bytes. \$\endgroup\$ – Arnauld Sep 30 '18 at 6:15
  • \$\begingroup\$ @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! \$\endgroup\$ – Neil Sep 30 '18 at 18:31
1
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ This code is failing on TIO for [1,10,100]. It's returning 126 instead of 99. \$\endgroup\$ – Meerkat Nov 7 '18 at 14:07
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

Ruby, 38 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

PowerShell, 52 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Perl 5 -ap, 39 bytes

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

Try it online!

\$\endgroup\$
-1
\$\begingroup\$

JavaScript (Node.js), 52 bytes

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

Try it online!

\$\endgroup\$
-1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Note that input via a pre-declared variable is not allowed. Additionally, you can shorten your variable names a bit \$\endgroup\$ – Jo King Oct 8 '18 at 9:44
  • \$\begingroup\$ sure, i will do it shortly. \$\endgroup\$ – Syed Hamza Hassan Oct 8 '18 at 9:50
  • \$\begingroup\$ You can do a=s=0 and -(x-a[d])+s, along with multiple other things. \$\endgroup\$ – S.S. Anne Feb 5 at 17:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.