aboutsummaryrefslogtreecommitdiff
path: root/min_cost_arr_equal.c
diff options
context:
space:
mode:
Diffstat (limited to 'min_cost_arr_equal.c')
-rw-r--r--min_cost_arr_equal.c51
1 files changed, 51 insertions, 0 deletions
diff --git a/min_cost_arr_equal.c b/min_cost_arr_equal.c
new file mode 100644
index 0000000..74ff9ac
--- /dev/null
+++ b/min_cost_arr_equal.c
@@ -0,0 +1,51 @@
+// 2448. Minimum Cost to Make Array Equal
+#include <stdio.h>
+#include <stdlib.h>
+
+/*
+ * given two 0-indexed arrays 'nums' and 'cost' consisting each of 'n' positive
+ * integers. you can do the following operation any number of times:
+ * - increase or decrease any element of the array 'nums' by 1
+ * the cost of doing one operation on the i'th element is 'cost[i]'. return the
+ * minimum total cost such that all the elements of the array 'nums' become
+ * equal
+ */
+
+long long helper(int *nums, int nums_size, int *cost, int mid) {
+ long long sum = 0;
+ for (int i = 0; i < nums_size; i++) {
+ long long k = abs(nums[i] - mid);
+ sum += k * cost[i];
+ }
+ return sum;
+}
+
+long long minCost(int *nums, int nums_size, int *cost, int cost_size) {
+ long long low = 1, high = 1e6;
+ while (low <= high) {
+ int mid = (low + high) / 2;
+ long long y1 = helper(nums, nums_size, cost, mid);
+ if (low == high)
+ return y1;
+ long long y2 = helper(nums, nums_size, cost, mid + 1);
+ long long y3 = helper(nums, nums_size, cost, mid - 1);
+ if (y2 >= y1 && y1 <= y3)
+ return y1;
+ if (y2 < y1) {
+ high = mid;
+ continue;
+ }
+ if (y3 < y1) {
+ low = mid;
+ continue;
+ }
+ }
+ return 0;
+}
+
+int main() {
+ int n1[] = {1, 3, 5, 2}, c1[] = {2, 3, 1, 14};
+ int n2[] = {2, 2, 2, 2, 2}, c2[] = {4, 2, 8, 1, 3};
+ printf("%lld\n", minCost(n1, 4, c1, 4)); // expect: 8
+ printf("%lld\n", minCost(n2, 5, c2, 5)); // expect: 0
+}