aboutsummaryrefslogtreecommitdiff
path: root/min_ops_arr_elem_zero.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-09-05 22:09:03 -0600
committerJack Sangdahl <[email protected]>2025-09-05 22:09:03 -0600
commit8eca342b99ab30a60285fc842f0229ab60ba2bcc (patch)
treef440631fa4ce02042a27db631f47fc2e5abec366 /min_ops_arr_elem_zero.c
parent4efcf3f8df8a89adbef6018a9d2b9c1a2fee7ddf (diff)
downloadleetcode-8eca342b99ab30a60285fc842f0229ab60ba2bcc.tar.gz
leetcode-8eca342b99ab30a60285fc842f0229ab60ba2bcc.zip
3495. minimum operations to make array elements zero
Diffstat (limited to 'min_ops_arr_elem_zero.c')
-rw-r--r--min_ops_arr_elem_zero.c43
1 files changed, 43 insertions, 0 deletions
diff --git a/min_ops_arr_elem_zero.c b/min_ops_arr_elem_zero.c
new file mode 100644
index 0000000..41e7e66
--- /dev/null
+++ b/min_ops_arr_elem_zero.c
@@ -0,0 +1,43 @@
+// 3495. Minimum Operations to Make Array Elements Zero
+#include "leetcode.h"
+
+/*
+ * you are given a 2d array 'queries' where 'queries[i]' is of the form '[l,
+ * r]'. each 'queries[i]' defines an array of integers 'nums' consisting of
+ * elements ranging from 'l' to 'r' both inclusive. in one operation you can
+ * select two integers 'a' and 'b' from the array and replace them with 'floor(a
+ * / 4)' and 'floor(b / 4)'. your task is to determine the minimum number of
+ * operations required to reduce all the elements of the array to zero for each
+ * query. return the sum of the results for all queries.
+ */
+
+long long count(long long a) {
+ long long res = 0, k = 1, v = 1;
+ while (a >= v * 4) {
+ res += (v * 4 - v) * k;
+ k++;
+ v *= 4;
+ }
+ return res + (a - v + 1) * k;
+}
+
+long long minOperations(int **queries, int queriesSize, int *queriesColSize) {
+ long long ans = 0;
+ for (int i = 0; i < queriesSize; i++)
+ ans += (count(queries[i][1]) - count(queries[i][0] - 1) + 1) / 2;
+ return ans;
+}
+
+int main() {
+ int q1i[2][2] = {{1, 2}, {2, 4}}, q2i[][2] = {{2, 6}};
+ struct two_d_arr *q1 =
+ two_d_arr_init(ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i);
+ struct two_d_arr *q2 =
+ two_d_arr_init(ARRAY_SIZE(q2i), ARRAY_SIZE(q2i[0]), q2i);
+ printf("%lld\n",
+ minOperations(q1->arr, q1->row_size, q1->col_size)); // expect: 3
+ printf("%lld\n",
+ minOperations(q2->arr, q2->row_size, q2->col_size)); // expect: 4
+ two_d_arr_free(q1);
+ two_d_arr_free(q2);
+}