In this Leetcode Minimum Moves to Equal Array Elements II problem solution Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.

In one move, you can increment or decrement an element of the array by 1.

Leetcode Minimum Moves to Equal Array Elements II problem solution


Problem solution in Python.

count = 0
    nums.sort()
    middle_element = nums[len(nums)//2]        
    for num in nums:
        count += abs(middle_element - num)     
    return count



Problem solution in Java.

public class Solution {
    public int minMoves2(int[] nums) {
        if (nums == null) return 0;
        
        Arrays.sort(nums);
        int k = (nums.length + 1) >> 1;
        int sum = 0;
        
        for (int i = 0; i< (nums.length >> 1); i++) {
            sum += nums[k+i] - nums[i];
        }
        return sum;      
    }
}


Problem solution in C++.

class Solution {
public:    
    int partition(vector<int> &nums, int l, int r) {
        int len = r - l + 1;
        int index = (rand() % len) + l;
        swap(nums[index], nums[r]);
        int pivot = nums[r];        
        int less = l;
        for (int i = l; i < r; i++) {
            if (nums[i] <= pivot) {
                swap(nums[i], nums[less++]);
            }
        }        
        swap(nums[less], nums[r]);        
        return less;
    }    
    int selectK(vector<int> &nums, int k, int l , int r) {
        if (l >= r) return l;        
        int pivot_index = partition(nums, l, r);        
        if (pivot_index - l + 1 == k) {
            return pivot_index;
        } else if (pivot_index - l + 1 < k) {
            return selectK(nums, k - (pivot_index - l + 1), pivot_index + 1, r);
        } else {
            return selectK(nums, k, l, pivot_index - 1);
        }
    }    
    int minMoves2(vector<int>& nums) {
        if (nums.empty()) return 0;        
        int median = nums.size() / 2;        
        int middle = nums[selectK(nums, median + 1, 0, nums.size() - 1)];
        int count = 0;
        for (int n : nums) {
            if (n > middle) {
                count += n - middle;
            } else {
                count += middle - n;
            }
        }        
        return count;
    }
};