142. Minimum Moves to Equal Array Elements II

Given an integer array nums, return the minimum number of moves to make all elements equal, where each move increments or decrements one element by 1. The optimal target is the median.

Input: An integer array.

Output: Integer — minimum moves.

Examples

Input: [1,2,3]
Output: 2
Explanation: Move to 2: |1-2|+|3-2|=2.

Input: [1,10,2,9]
Output: 16
Explanation: Median-based total.

Input: [1]
Output: 0
Explanation: Single element.

Constraints

• 1<=n<=10^5
• -10^9<=nums[i]<=10^9

Asked by