2448. Minimum Cost to Make Array Equal | Binary Search | Median | LeetCode Daily Challenge

[@harikrushnasuhagiya3925]

Osm Bro

[@deepcodes]

class Solution {
public:
long long getCost(vector& nums, vector& cost, int mid) {
long long currAns = 0;
for (int i = 0; i < nums.size(); i++) {
int diff = abs(nums[i] - mid);
currAns += 1L * diff*cost[i];
}
return currAns;
}
long long minCost(vector& nums, vector& cost) {
long long ans = 0;
int l = nums[0], h = nums[0];
for (auto n : nums) {
l = min(l, n);
h = max(h, n);
}
while (l < h) {
int mid = l + (h-l)/2;
long long curr1 = getCost(nums, cost, mid);
long long curr2 = getCost(nums, cost, mid+1);
ans = min(curr1, curr2);
if (curr1 > curr2) {
l = mid + 1;
}
else {
h = mid;
}
}
return ans;
}
};

[@deepcodes]

class Solution {
public:
long long getCost(vector& nums, vector& cost, int mid) {
long long currAns = 0;
for (int i = 0; i < nums.size(); i++) {
int diff = abs(nums[i] - mid);
currAns += 1L * diff*cost[i];
}
return currAns;
}
long long minCost(vector& nums, vector& cost) {
long long ans = 0;
int n = nums.size();
vectorv;
for (int i = 0; i < n; i++) {
v.push_back({nums[i], cost[i]});
}
sort(v.begin(), v.end());
long long totalN = 0;
for (int i = 0; i < n; i++) {
totalN += 1L * v[i].second;
}
long long median, currTotal = 0;
for (int i = 0; i < n && currTotal < (totalN+1)/2; i++) {
currTotal += 1L * v[i].second;
median = v[i].first;
}
cout

[@shikharshukla8836]

thank you

[@AluSoft]

awesome! I did using prefix sum, but I found your approach easier!

[@trishulcurtis1810]

Nice Explanation. How can you be sure about that the result value will be present in the input
array?

[@muditsrivastav3249]

why we are taking high = mid not mid-1

[@deepcodes]

while (l < h) {
//...
h = mid;
}
Or do this way
while (l

[@aadil4236]

took you long to upload the video today.