aboutsummaryrefslogtreecommitdiff
path: root/cycle_queries_tree.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-02-21 10:41:22 -0700
committerJack Sangdahl <[email protected]>2025-02-21 10:41:22 -0700
commiteb3697b5c7c80be7c0abf04524408f83cb4ed30d (patch)
tree26d10f344f9331600b2721982ea5adf4d1d565b4 /cycle_queries_tree.c
parent46d84341f48c823b6b0bd01a3092f364d187b59f (diff)
downloadleetcode-eb3697b5c7c80be7c0abf04524408f83cb4ed30d.tar.gz
leetcode-eb3697b5c7c80be7c0abf04524408f83cb4ed30d.zip
2509. cyclen length queries in a tree
Diffstat (limited to 'cycle_queries_tree.c')
-rw-r--r--cycle_queries_tree.c53
1 files changed, 53 insertions, 0 deletions
diff --git a/cycle_queries_tree.c b/cycle_queries_tree.c
new file mode 100644
index 0000000..d604e9f
--- /dev/null
+++ b/cycle_queries_tree.c
@@ -0,0 +1,53 @@
+// 2509. Cycle Length Queries in a Tree
+#include "leetcode.h"
+
+/*
+ * you are given an integer 'n'. there is a complete binary tree with '2^n - 1'
+ * nodes. the root of that tree is the node with the value 1, and every node
+ * with a value 'val' in the range '[1, 2^(n - 1) - 1]' has two children. you
+ * are also given a 2d integer array 'queries' of length 'm' where 'queries[i] =
+ * [a_i, b_i]'. for each query, add an edge between the nodes with values 'a_i'
+ * and 'b_i', find the length of the cycle in the graph, and remove the added
+ * edge between nodes with values 'a_i' and 'b_i'.
+ */
+
+int search(int a, int b) {
+ int cnt = 0;
+ while (a != b) {
+ if (a < b)
+ b /= 2;
+ else
+ a /= 2;
+ cnt++;
+ }
+ return ++cnt;
+}
+
+int *cycleLengthQueries(int n, int **queries, int queriesSize,
+ int *queriesColSize, int *returnSize) {
+ int *ans = (int *)malloc(queriesSize * sizeof(int));
+ *returnSize = queriesSize;
+ for (int i = 0; i < queriesSize; i++)
+ ans[i] = search(queries[i][0], queries[i][1]);
+ return ans;
+}
+
+int main() {
+ int q1i[3][2] = {{5, 3}, {4, 7}, {2, 3}}, rs1;
+ int q2i[1][2] = {{1, 2}}, rs2;
+ struct two_d_arr q1, q2;
+ two_d_arr_init(&q1, ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i);
+ two_d_arr_init(&q2, ARRAY_SIZE(q2i), ARRAY_SIZE(q2i[0]), q2i);
+ int *clq1 = cycleLengthQueries(3, q1.arr, q1.row_size, q1.col_size, &rs1);
+ int *clq2 = cycleLengthQueries(2, q2.arr, q2.row_size, q2.col_size, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", clq1[i]); // expect: 4 5 3
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", clq2[i]); // expect: 2
+ printf("\n");
+ free(clq1);
+ free(clq2);
+ two_d_arr_free(&q1);
+ two_d_arr_free(&q2);
+}