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

23 Answers 23

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

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

05AB1E, 4 bytes

ÅmαO

Try it online!

Explanation

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

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

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

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.

  • -2 bytes by declaring r within the first map. – Shaggy Sep 29 at 16:24

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.

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.

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.

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

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
  • 1
    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.) – Misha Lavrov Sep 30 at 0:51

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 */
}

R, 29 bytes

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

Try it online!

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

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

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

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!

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

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
}

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)

PHP, 69 bytes

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

anonymous function. Try it online.

  • @Progrock Input: *) A non-empty array a of integers *) Optionally, the length of a . – Titus Nov 8 at 14:28
  • @Progrock A post-decrement does the same trick. But thanks for the hint. – Titus Nov 8 at 21:56

JavaScript (Node.js), 52 bytes

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

Try it online!

Java (JDK), 112 bytes

Golfed

private static int e(int[]a){int s=0;for(int i:a){s+=i;}s/=a.length;int r=0;for(int i:a){r+=abs(s-i);}return r;}

Ungolfed

private static int equalize(int[] array) {
    int sum = 0;
    for (int i : array) {
        sum += i;
    }
    sum /= array.length;
    int ret = 0;
    for (int i : array) {
        ret += abs(sum-i);
    }
    return ret;
}
  • 1
    Welcome to PPCG! Unfortunately, your solution fails for the input [1,1,4] (returns 4, but the answer is 3). – Delfad0r Oct 8 at 7:58
  • 1
    A note that you seem to be using the mean of the array, rather than the median – Jo King Oct 8 at 9:01

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

  • Note that input via a pre-declared variable is not allowed. Additionally, you can shorten your variable names a bit – Jo King Oct 8 at 9:44
  • sure, i will do it shortly. – Syed Hamza Hassan Oct 8 at 9:50

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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