Sponsored
Sponsored
To minimize the number of moves, the optimal strategy is to move all numbers to the median of the array. The median minimizes the sum of absolute deviations (L1 norm), which provides the least number of moves required to make all elements equal. By sorting the array and picking the middle element (or the average of two middle elements for an even-sized array), we can find the median efficiently.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) for in-place operations aside from sort implementation.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 return (*(int *)a - *(int *)b);
6}
7
8int minMoves2(int* nums, int numsSize) {
9 qsort(nums, numsSize, sizeof(int), compare);
10 int median = nums[numsSize / 2];
11 int moves = 0;
12 for (int i = 0; i < numsSize; i++) {
13 moves += abs(nums[i] - median);
14 }
15 return moves;
16}
17
18int main() {
19 int nums[] = {1, 2, 3};
20 int size = sizeof(nums) / sizeof(nums[0]);
21 printf("%d\n", minMoves2(nums, size));
22 return 0;
23}The solution sorts the array and then calculates the number of moves needed by summing the absolute differences between each element and the median. The C standard library function qsort is used for sorting.
This approach uses a two-pointer technique on a sorted version of the array to calculate the minimum moves. We initialize two pointers, one at the beginning and the other at the end of the sorted array. By incrementing the left pointer and decrementing the right pointer, we accumulate the number of moves required to make each element pair equal.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1).
1#include <vector>
#include <algorithm>
int minMoves2(std::vector<int>& nums) {
std::sort(nums.begin(), nums.end());
int moves = 0;
int i = 0, j = nums.size() - 1;
while (i < j) {
moves += nums[j] - nums[i];
i++; j--;
}
return moves;
}
int main() {
std::vector<int> nums = {1, 10, 2, 9};
std::cout << minMoves2(nums) << std::endl;
return 0;
}The C++ code applies a two-pointer technique after sorting the array to minimize the required moves between pairs.