[LeetCode] 453. Minimum Moves to Equal Array Elements

轉自LeetCode

Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n -1 elements by 1.

Example:

Input:
[1,2,3]
Output:
3
Explanation:
Only three moves are needed (remember each move increments two elements):
[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

<Solution>

We should think reversely.

An array which has n elements. Each move will increase n - 1 elements by 1. This also means that each move will decrease 1 element by 1.

Therefore, we only neet do know how many moves of each element to be decreased by 1 will equal the min number and sum them up. Do some math and the ans will be sum-min * length

Eg. [1, 2, 3]

(1–1) + (2–1) + (3–1) = (1 + 2 + 3)-1 * 3

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.