LeetCode: Minimum Moves to Equal Array Elements
Problem: https://leetcode.com/problems/minimum-moves-to-equal-array-elements/, or copied/pasted here:
This is an interesting problem that can be solved more simplistically than the problem suggests. Don't try to follow the strategy implied by the problem description - it is misleading and will make your code convoluted and inefficient. Here are few insights that will lead to a 3-liner solution:
Insight 1: when the problem says "incrementing n-1 elements by 1", notice that this is the same as saying "decrementing 1 element by 1". If you're increasing n-1 elements by 1 (meaning increasing all but one element), it is the same as decreasing that one element by 1. This will make the solution much easier.
Insight 2: given a certain element A, and using "Insight 1", in order for all the elements to be the same at the end, inevitably we'll have to transform A into the minimum element in the array. Hence, for a given element A, there will be at least A - Min(Array) moves to get to the solution. In fact the solution will then be the summation of Ai - Min(Array) for every Ai in the array.
Insight 3: given "Insight 2", we can do some math to land at the final formula to solve the problem in linear time:
Solution = A1 - Min(Array) + A2 - Min(Array) + ... + An - Min(Array)
Solution = (A1 + A2 + A3 + ... + An) - n*Min(Array)
Solution = Sum(Array) - n*Min(Array)
The last expression is the solution. The 3-liner code becomes:
public int MinMoves(int[] nums)
{
int sum = 0, min = Int32.MaxValue;
for (int i = 0; i < nums.Length; sum += nums[i++]) min = (nums[i] < min) ? nums[i] : min;
return sum - nums.Length * min;
}
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]
This is an interesting problem that can be solved more simplistically than the problem suggests. Don't try to follow the strategy implied by the problem description - it is misleading and will make your code convoluted and inefficient. Here are few insights that will lead to a 3-liner solution:
Insight 1: when the problem says "incrementing n-1 elements by 1", notice that this is the same as saying "decrementing 1 element by 1". If you're increasing n-1 elements by 1 (meaning increasing all but one element), it is the same as decreasing that one element by 1. This will make the solution much easier.
Insight 2: given a certain element A, and using "Insight 1", in order for all the elements to be the same at the end, inevitably we'll have to transform A into the minimum element in the array. Hence, for a given element A, there will be at least A - Min(Array) moves to get to the solution. In fact the solution will then be the summation of Ai - Min(Array) for every Ai in the array.
Insight 3: given "Insight 2", we can do some math to land at the final formula to solve the problem in linear time:
Solution = A1 - Min(Array) + A2 - Min(Array) + ... + An - Min(Array)
Solution = (A1 + A2 + A3 + ... + An) - n*Min(Array)
Solution = Sum(Array) - n*Min(Array)
The last expression is the solution. The 3-liner code becomes:
public int MinMoves(int[] nums)
{
int sum = 0, min = Int32.MaxValue;
for (int i = 0; i < nums.Length; sum += nums[i++]) min = (nums[i] < min) ? nums[i] : min;
return sum - nums.Length * min;
}
It beats near 90% of the other C# submissions (it surprises me that there are still 10% faster than that). Cheers, Marcelo.
Brilliant insight and a clever solution! Originally I, being a lazy potato, solved this problem using a naive 2-pass solution:
ReplyDeleteint minMovesNaive(const vector& nums) {
int base = *min_element(nums.cbegin(), nums.cend());
return accumulate(nums.cbegin(), nums.cend(), 0) - base * nums.size();
}
and it ran in 69ns, but than I saw your solution and thought - ha, indeed, why do I use 2-passes, where 1 would suffice? Saw I rewrote my original solution with something like this:
int minMoves(vector& nums) {
int base = numeric_limits::max();
int sum = 0;
for (int i = 0; i < nums.size(); ++i) {
sum += nums[i];
base = min(base, nums[i]);
}
return sum - base * nums.size();
}
which is pretty much exactly what you have, except more lines, since I like to segregate commands and queries and being very explicit (verbose :)). Anyways, the strange thing happened when I submitted this solution - it took 89ms, which is counter-intuitive. How on earth 2-passes could be faster than 1? So I looked at the disassembly of both functions (https://godbolt.org/g/pE66rM) and immediately stumbled upon the answer:
...
movdqa xmm1, xmm0
psrldq xmm1, 8
paddd xmm0, xmm1
movdqa xmm1, xmm0
psrldq xmm1, 4
paddd xmm0, xmm1
...
This is just a small excerpt from a 2-pass implementation, which overall is much longer and more complex, but it reveals that a compiler is able to vectorize the 2-pass implementation, which means that summation can be performed roughly 4 times faster (xmm registers are 16 bytes, so summation can happen on 4 integers at the same time). The moral of the story is that our assumption about performance are frequently wrong and it's always good to measure before trying to optimize something :)
Thanks for reminding me about the beauty of this problem!
FYI: I liked this problem so much that I even started a new blog and published a post about it - https://performance-anecdotes.blogspot.com/2016/12/when-its-faster-to-do-more-work.html
DeleteWow that was really something new to me! Great analysis going deep!!!!
Deletenext time, I might overcome my advanced laziness and profile the code to at least create an illusion that I know what I'm talking about :)
Delete