Algorithm to find the minimum number of moves required to bring all elements to the same number (Python)?

Question

Python

I ask you to help solve the problem, or at least hint in which direction to "dig". Given an array of integers. It is necessary to find the minimum number of moves required to bring all elements of the array to the same number. In one move, you can decrease or increase one element of the array by 1. Everything is quite simple as long as the array looks like this:

import math

nums = [1, 10, 2, 9]
result_digit = math.ceil((max(nums))/2)
count = 0
for id, i in enumerate(nums):
    while i != result_digit:
         if i < result_digit:
             i += 1
             count += 1
         elif i > result_digit:
              i -= 1
              count += 1
         else:
            nums[id] = i
    print(count)

But, if nums = [0, 0, 0, 1] then this algorithm is not suitable and will output 3 instead of 1. The array can be any length.

Answer 1

Look for the median of your set of numbers. This will be the starting point, to which you will need to finish off all the numbers.
And then you just sum up the modules of the difference of each element of the set with this number.
If you need more details - tell
PS Re-read the second answer - basically the same thing.

Answer 2

First, your algorithm doesn't need a while loop at all. How many +1 operations are needed to get a+12345 from a? Exactly 12345. You just need to subtract one number from another.
Further, the thought should be this: Now you know how many operations are needed to bring all the numbers in the array to X. Question: how many operations will you need to bring all the numbers to X + 1? (Hint - if the number was less than X, now it will take 1 operation more. If the number was more than X, then it will take 1 operation less).
Now you need to look, think and choose the optimal X, to which you will give all the numbers. Your option with max/2 is not optimal.

Answer 3

We need to find the sum of all abs(a[i] - X), where X is the same number that will be in the middle if the array is sorted (that is, the median).
This number, if I'm not mistaken, can be found linearly using QuickSelect. If the array cannot be shuffled, you will have to make a copy of it.

Answer 4

Visually, you can imagine: a bunch of points was accidentally thrown onto the plane)
X and Y axes, X reception is not important in this case. Y - values ​​in the array.
It is necessary to move the horizontal line in such a way that the sum of the distances from each of the points to this line is minimal. Its Y will be the value to which the rest of the points "step".
This is a simplified version of linear regression, by the way.

Answer 5

If the number of array elements is odd, then the value to which the elements must be reduced is equal to the value of the strictly middle element (the median of the array).
If the number of array elements is even, then any value between the two middle elements, inclusive, is suitable as the final value.
To see this - just think about how the required number of alignment steps changes if you move the final value by 1 to the right or left, depending on how many elements are on the right and how many are on the left.