Equalize the array

Clash Royale CLAN TAG#URR8PPP

up vote
6
down vote

favorite

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

code-golf array-manipulation

share|improve this question

asked 52 mins ago

Delfad0r

688110

add a comment | 

up vote
6
down vote

favorite

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

code-golf array-manipulation

share|improve this question

asked 52 mins ago

Delfad0r

688110

add a comment | 

up vote
6
down vote

favorite

up vote
6
down vote

favorite

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

code-golf array-manipulation

share|improve this question

asked 52 mins ago

Delfad0r

688110

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

code-golf array-manipulation

code-golf array-manipulation

share|improve this question

asked 52 mins ago

Delfad0r

688110

share|improve this question

asked 52 mins ago

Delfad0r

688110

share|improve this question

share|improve this question

asked 52 mins ago

Delfad0r

688110

asked 52 mins ago

Delfad0r

688110

asked 52 mins ago

Delfad0r

688110

688110

add a comment | 

add a comment | 

5 Answers
5

active

oldest

votes

up vote
2
down vote

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.

share|improve this answer

answered 16 mins ago

Mr. Xcoder

30.6k758194

add a comment | 

up vote
2
down vote

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

share|improve this answer

edited 13 mins ago

answered 37 mins ago

user202729

12.9k12449

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Random comment: Median is a bit too hard for some esoteric languages.
  – user202729
  35 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Looking around a bit, the only submission in esoteric language in the "compute the median" challenge is WW's Brain-Flak one.
  – user202729
  25 mins ago
  
  

  
  
  
  

add a comment | 

up vote
2
down vote

05AB1E, 4 bytes

ÅmαO

Try it online!

Explanation

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

share|improve this answer

answered 12 mins ago

Emigna

43.4k431131

add a comment | 

up vote
1
down vote

JavaScript (ES6), 60 bytes

f=(a,k=0,p)=>a.map(n=>m+=n>k?n-k:k-n,m=0)|m>p?~~p:f(a,k+1,m)

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 recursively try all target values $k ge 0$ and stop as soon as the new result $m$ is worse than the previous one $p$.

share|improve this answer

edited 1 min ago

answered 28 mins ago

Arnauld

65.4k581277

add a comment | 

up vote
0
down vote

Perl 6, 29 bytes

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

Try it online!

share|improve this answer

edited 6 mins ago

answered 32 mins ago

Jo King

16.4k24190

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "200"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f173038%2fequalize-the-array%23new-answer', 'question_page');

);

Post as a guest

Name Email

5 Answers
5

active

oldest

votes

5 Answers
5

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
2
down vote

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.

share|improve this answer

answered 16 mins ago

Mr. Xcoder

30.6k758194

add a comment | 

up vote
2
down vote

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.

share|improve this answer

answered 16 mins ago

Mr. Xcoder

30.6k758194

add a comment | 

up vote
2
down vote

up vote
2
down vote

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.

share|improve this answer

answered 16 mins ago

Mr. Xcoder

30.6k758194

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.

share|improve this answer

answered 16 mins ago

Mr. Xcoder

30.6k758194

share|improve this answer

share|improve this answer

answered 16 mins ago

Mr. Xcoder

30.6k758194

answered 16 mins ago

Mr. Xcoder

30.6k758194

answered 16 mins ago

Mr. Xcoder

30.6k758194

30.6k758194

add a comment | 

add a comment | 

up vote
2
down vote

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

share|improve this answer

edited 13 mins ago

answered 37 mins ago

user202729

12.9k12449

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Random comment: Median is a bit too hard for some esoteric languages.
  – user202729
  35 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Looking around a bit, the only submission in esoteric language in the "compute the median" challenge is WW's Brain-Flak one.
  – user202729
  25 mins ago
  
  

  
  
  
  

add a comment | 

up vote
2
down vote

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

share|improve this answer

edited 13 mins ago

answered 37 mins ago

user202729

12.9k12449

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Random comment: Median is a bit too hard for some esoteric languages.
  – user202729
  35 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Looking around a bit, the only submission in esoteric language in the "compute the median" challenge is WW's Brain-Flak one.
  – user202729
  25 mins ago
  
  

  
  
  
  

add a comment | 

up vote
2
down vote

up vote
2
down vote

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

share|improve this answer

edited 13 mins ago

answered 37 mins ago

user202729

12.9k12449

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

share|improve this answer

edited 13 mins ago

answered 37 mins ago

user202729

12.9k12449

share|improve this answer

share|improve this answer

edited 13 mins ago

edited 13 mins ago

edited 13 mins ago

answered 37 mins ago

user202729

12.9k12449

answered 37 mins ago

user202729

12.9k12449

answered 37 mins ago

user202729

12.9k12449

12.9k12449

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Random comment: Median is a bit too hard for some esoteric languages.
  – user202729
  35 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Looking around a bit, the only submission in esoteric language in the "compute the median" challenge is WW's Brain-Flak one.
  – user202729
  25 mins ago
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Random comment: Median is a bit too hard for some esoteric languages.
  – user202729
  35 mins ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Looking around a bit, the only submission in esoteric language in the "compute the median" challenge is WW's Brain-Flak one.
  – user202729
  25 mins ago
  
  

  
  
  
  

Random comment: Median is a bit too hard for some esoteric languages.
– user202729
35 mins ago

Random comment: Median is a bit too hard for some esoteric languages.
– user202729
35 mins ago

Looking around a bit, the only submission in esoteric language in the "compute the median" challenge is WW's Brain-Flak one.
– user202729
25 mins ago

Looking around a bit, the only submission in esoteric language in the "compute the median" challenge is WW's Brain-Flak one.
– user202729
25 mins ago

add a comment | 

up vote
2
down vote

05AB1E, 4 bytes

ÅmαO

Try it online!

Explanation

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

share|improve this answer

answered 12 mins ago

Emigna

43.4k431131

add a comment | 

up vote
2
down vote

05AB1E, 4 bytes

ÅmαO

Try it online!

Explanation

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

share|improve this answer

answered 12 mins ago

Emigna

43.4k431131

add a comment | 

up vote
2
down vote

up vote
2
down vote

05AB1E, 4 bytes

ÅmαO

Try it online!

Explanation

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

share|improve this answer

answered 12 mins ago

Emigna

43.4k431131

05AB1E, 4 bytes

ÅmαO

Try it online!

Explanation

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

share|improve this answer

answered 12 mins ago

Emigna

43.4k431131

share|improve this answer

share|improve this answer

answered 12 mins ago

Emigna

43.4k431131

answered 12 mins ago

Emigna

43.4k431131

answered 12 mins ago

Emigna

43.4k431131

43.4k431131

add a comment | 

add a comment | 

up vote
1
down vote

JavaScript (ES6), 60 bytes

f=(a,k=0,p)=>a.map(n=>m+=n>k?n-k:k-n,m=0)|m>p?~~p:f(a,k+1,m)

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 recursively try all target values $k ge 0$ and stop as soon as the new result $m$ is worse than the previous one $p$.

share|improve this answer

edited 1 min ago

answered 28 mins ago

Arnauld

65.4k581277

add a comment | 

up vote
1
down vote

JavaScript (ES6), 60 bytes

f=(a,k=0,p)=>a.map(n=>m+=n>k?n-k:k-n,m=0)|m>p?~~p:f(a,k+1,m)

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 recursively try all target values $k ge 0$ and stop as soon as the new result $m$ is worse than the previous one $p$.

share|improve this answer

edited 1 min ago

answered 28 mins ago

Arnauld

65.4k581277

add a comment | 

up vote
1
down vote

up vote
1
down vote

JavaScript (ES6), 60 bytes

f=(a,k=0,p)=>a.map(n=>m+=n>k?n-k:k-n,m=0)|m>p?~~p:f(a,k+1,m)

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 recursively try all target values $k ge 0$ and stop as soon as the new result $m$ is worse than the previous one $p$.

share|improve this answer

edited 1 min ago

answered 28 mins ago

Arnauld

65.4k581277

JavaScript (ES6), 60 bytes

f=(a,k=0,p)=>a.map(n=>m+=n>k?n-k:k-n,m=0)|m>p?~~p:f(a,k+1,m)

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 recursively try all target values $k ge 0$ and stop as soon as the new result $m$ is worse than the previous one $p$.

share|improve this answer

edited 1 min ago

answered 28 mins ago

Arnauld

65.4k581277

share|improve this answer

share|improve this answer

edited 1 min ago

edited 1 min ago

edited 1 min ago

answered 28 mins ago

Arnauld

65.4k581277

answered 28 mins ago

Arnauld

65.4k581277

answered 28 mins ago

Arnauld

65.4k581277

65.4k581277

add a comment | 

add a comment | 

up vote
0
down vote

Perl 6, 29 bytes

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

Try it online!

share|improve this answer

edited 6 mins ago

answered 32 mins ago

Jo King

16.4k24190

add a comment | 

up vote
0
down vote

Perl 6, 29 bytes

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

Try it online!

share|improve this answer

edited 6 mins ago

answered 32 mins ago

Jo King

16.4k24190

add a comment | 

up vote
0
down vote

up vote
0
down vote

Perl 6, 29 bytes

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

Try it online!

share|improve this answer

edited 6 mins ago

answered 32 mins ago

Jo King

16.4k24190

Perl 6, 29 bytes

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

Try it online!

share|improve this answer

edited 6 mins ago

answered 32 mins ago

Jo King

16.4k24190

share|improve this answer

share|improve this answer

edited 6 mins ago

edited 6 mins ago

edited 6 mins ago

answered 32 mins ago

Jo King

16.4k24190

answered 32 mins ago

Jo King

16.4k24190

answered 32 mins ago

Jo King

16.4k24190

16.4k24190

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f173038%2fequalize-the-array%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email