Sponsored
Sponsored
This approach involves treating the problem as a minimization problem where the minimum total cost is calculated by iterating over potential target values using binary search. At each step, the cost to make all elements equal to a proposed target is calculated, and the goal is to find the target that results in the minimal cost. By narrowing the range of potential target values using binary search, this approach efficiently finds the optimal target.
Time Complexity: O(n log(MAX_DIFF)), where MAX_DIFF is the range of possible numbers.
Space Complexity: O(1) since it only uses a fixed amount of extra space.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <climits>
5
6using namespace std;
7
8long long calculateCost(const vector<int>& nums, const vector<int>& cost, int target) {
9 long long totalCost = 0;
10 for (size_t i = 0; i < nums.size(); ++i) {
11 totalCost += abs(nums[i] - target) * static_cast<long long>(cost[i]);
12 }
13 return totalCost;
14}
15
16long long minCost(vector<int>& nums, vector<int>& cost) {
17 int minNum = *min_element(nums.begin(), nums.end());
18 int maxNum = *max_element(nums.begin(), nums.end());
19 long long result = LLONG_MAX;
20 while (minNum <= maxNum) {
21 int midNum = minNum + (maxNum - minNum) / 2;
22 long long costMid = calculateCost(nums, cost, midNum);
23 long long costMidPlusOne = calculateCost(nums, cost, midNum + 1);
24 result = min(costMid, costMidPlusOne);
25 if (costMid < costMidPlusOne) {
26 maxNum = midNum - 1;
27 } else {
28 minNum = midNum + 1;
29 }
30 }
31 return result;
32}
33
34int main() {
35 vector<int> nums = {1, 3, 5, 2};
36 vector<int> cost = {2, 3, 1, 14};
37 cout << "Minimum cost: " << minCost(nums, cost) << endl;
38 return 0;
39}This C++ solution is similar to the C implementation. It uses std::min_element and std::max_element from the STL to find the minimum and maximum bounds for binary search, improving readability and safety. The key logic for binary searching over potential target values to minimize cost remains identical.
The main idea is to use the concept of a weighted median to find the optimal target, a value to which all elements should be equalized to minimize cost. The weighted median is the best choice for minimizing the cost because it balances out the costs by taking into account where the bulk of weights lie. By considering each element's weight (cost), the weighted median is a statistically optimal choice that minimizes the total cost for the adjustment.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for auxiliary space used in sorting.
1def min_cost(nums, cost):
2 zipped_pairs = sorted(zip(
This Python solution involves sorting an array of pairs [num, cost], aiming to identify the weighted median. We accumulate the weights and find a point where the accumulated weight is equal to or exceeds half the total weight, signifying the median. That value is used as the target, minimizing the total cost of modification via a single pass.