aboutsummaryrefslogtreecommitdiff
path: root/min_deviation_arr.c
diff options
context:
space:
mode:
Diffstat (limited to 'min_deviation_arr.c')
-rw-r--r--min_deviation_arr.c88
1 files changed, 88 insertions, 0 deletions
diff --git a/min_deviation_arr.c b/min_deviation_arr.c
new file mode 100644
index 0000000..5d00d56
--- /dev/null
+++ b/min_deviation_arr.c
@@ -0,0 +1,88 @@
+// 1675. Minimize Deviation in Array
+#include <stdio.h>
+
+#define SWAP(x, y) (x ^= y ^= x ^= y)
+#define MIN(a, b) ((a < b) ? a : b)
+
+/*
+ * the deviation of the array is the maximum difference between any two elements
+ * in the array. return minimum deviation the array can have after performing
+ * 'nums' ops.
+ */
+
+void check_larger(int *h, int posi) {
+ for (int cmp; posi >= 4; posi = cmp) {
+ cmp = (posi >> 2 << 1) + 1;
+ if (h[posi] > h[cmp])
+ SWAP(h[posi], h[cmp]);
+ else
+ break;
+ }
+}
+
+void check_smaller(int *h, int posi) {
+ for (int cmp; posi >= 4; posi = cmp) {
+ cmp = posi >> 2 << 1;
+ if (h[posi] < h[cmp])
+ SWAP(h[posi], h[cmp]);
+ else
+ break;
+ }
+}
+
+void insert(int *h, int top, int data) {
+ h[top] = data;
+ if (!(top & 1)) {
+ if (h[top] > h[top >> 1])
+ check_larger(h, top);
+ else
+ check_smaller(h, top);
+ } else {
+ if (h[top] < h[top - 1]) {
+ SWAP(h[top], h[top - 1]);
+ check_smaller(h, top - 1);
+ } else
+ check_larger(h, top);
+ }
+}
+
+void delete_max(int *h, int *top) {
+ h[3] = h[(*top)--];
+ int par = 3, chi = 5;
+ while (chi <= (*top)) {
+ if (chi + 2 <= (*top) && h[chi + 2] > h[chi])
+ chi += 2;
+ if (h[chi] > h[par]) {
+ SWAP(h[chi], h[par]);
+ par = chi;
+ chi = (chi << 1) - 1;
+ } else
+ break;
+ }
+ if (h[par] < h[par - 1])
+ SWAP(h[par], h[par - 1]);
+}
+
+int minimumDeviation(int *nums, int numsSize) {
+ int h[numsSize + 2], top = 1, ans;
+ for (int i = 0; i < numsSize; i++) {
+ if (nums[i] & 1)
+ nums[i] <<= 1;
+ insert(h, ++top, nums[i]);
+ }
+ ans = h[3] - h[2];
+ while (!(h[3] & 1)) {
+ int t = h[3] >> 1;
+ delete_max(h, &top);
+ insert(h, ++top, t);
+ ans = MIN(ans, h[3] - h[2]);
+ }
+ return ans;
+}
+
+int main() {
+ int n1[] = {1, 2, 3, 4}, n2[] = {4, 1, 5, 20, 3}, n3[] = {2, 10, 8};
+ printf("%d\n", minimumDeviation(n1, 4)); // expect: 1
+ printf("%d\n", minimumDeviation(n2, 5)); // expect: 3
+ printf("%d\n", minimumDeviation(n3, 3)); // expect: 3
+}