aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-21 07:43:40 -0700
committerJack Sangdahl <[email protected]>2024-12-21 07:43:40 -0700
commitc4bf635f931df151edbbbf47be3b37c730d9beed (patch)
tree57a567e7c59903c94c08dcd208647245980b5c96
parent4d70be0e550fcc570dbde58c4001e074e7cf357a (diff)
downloadleetcode-c4bf635f931df151edbbbf47be3b37c730d9beed.tar.gz
leetcode-c4bf635f931df151edbbbf47be3b37c730d9beed.zip
2872. maximum number of k-divisible components
-rw-r--r--max_num_k_div_comp.c73
-rw-r--r--max_num_k_div_comp.py69
2 files changed, 142 insertions, 0 deletions
diff --git a/max_num_k_div_comp.c b/max_num_k_div_comp.c
new file mode 100644
index 0000000..c57b983
--- /dev/null
+++ b/max_num_k_div_comp.c
@@ -0,0 +1,73 @@
+// 2872. Maximum Number of K-Divisible Components
+#include "leetcode.h"
+
+/*
+ * there is an undirected tree with 'n' nodes labeled from 0 to 'n - 1'. you are
+ * given the integer 'n' and a 2d integer array 'edges' of length 'n - 1', where
+ * 'edges[i] = [a_i, b_i]' indicates that there is an edge between nodes 'a_i'
+ * and 'b_i' in the tree. you are also given a 0-indexed integer array 'values'
+ * of length 'n' where 'values[i]' is the value associated with the i'th node
+ * and an integer 'k'. a valid split of the tree is obtained by removing any set
+ * of edges, possibly empty, from the tree such that the resulting components
+ * all have values thatare divisible by 'k', where the value of a connected
+ * component is the sum of the values of its node. return the maximum number of
+ * components in any valid split
+ */
+
+struct vec {
+ int *arr;
+ int size;
+};
+
+void push(struct vec *a, int val) {
+ a->arr = (int *)realloc(a->arr, (a->size + 1) * sizeof(int));
+ a->arr[a->size] = val;
+ ++a->size;
+}
+
+int dfs(int node, int parent, struct vec *adj, int *vals, int k, int *matches,
+ int n) {
+ int sum = 0, neighbour = adj[node].size;
+ for (int i = 0; i < neighbour; ++i) {
+ int n_node = adj[node].arr[i];
+ if (n_node == parent)
+ continue;
+ sum += dfs(n_node, node, adj, vals, k, matches, n);
+ }
+ sum += vals[node];
+ sum %= k;
+ if (!sum)
+ ++(*matches);
+ return sum;
+}
+
+int maxKDivisibleComponents(int n, int **edges, int edgesSize,
+ int *edgesColSize, int *values, int valuesSize,
+ int k) {
+ struct vec *adj = (struct vec *)malloc(n * sizeof(struct vec));
+ for (int i = 0; i < n; ++i)
+ adj[i] = (struct vec){(int *)malloc(0 * sizeof(int)), 0};
+ for (; edgesSize; ++edges, --edgesSize) {
+ int first = (*edges)[0], second = (*edges)[1];
+ push(adj + first, second);
+ push(adj + second, first);
+ }
+ int matches = 0;
+ dfs(0, -1, adj, values, k, &matches, n);
+ return matches;
+}
+
+int main() {
+ int e1i[4][2] = {{0, 2}, {1, 2}, {1, 3}, {2, 4}}, v1[] = {1, 8, 1, 4, 4};
+ int e2i[6][2] = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}},
+ v2[] = {3, 0, 6, 1, 5, 2, 1};
+ struct two_d_arr e1, e2;
+ two_d_arr_init(&e1, 4, 2, e1i);
+ two_d_arr_init(&e2, 6, 2, e2i);
+ printf("%d\n", maxKDivisibleComponents(5, e1.arr, e1.row_size, e1.col_size,
+ v1, ARRAY_SIZE(v1), 6)); // expect: 2
+ printf("%d\n", maxKDivisibleComponents(7, e2.arr, e2.row_size, e2.col_size,
+ v2, ARRAY_SIZE(v2), 3)); // expect: 2
+ two_d_arr_free(&e1);
+ two_d_arr_free(&e2);
+}
diff --git a/max_num_k_div_comp.py b/max_num_k_div_comp.py
new file mode 100644
index 0000000..f85ad97
--- /dev/null
+++ b/max_num_k_div_comp.py
@@ -0,0 +1,69 @@
+# 2872. Maximum Number of K-Divisible Components
+from collections import defaultdict, deque
+
+"""
+there is an undirected tree with 'n' nodes labeled from 0 to 'n - 1'. you are
+given the integer 'n' and a 2d integer array 'edges' of length 'n - 1', where
+'edges[i] = [a_i, b_i]' indicates that there is an edge between nodes 'a_i'
+and 'b_i' in the tree. you are also given a 0-indexed integer array 'values'
+of length 'n' where 'values[i]' is the value associated with the i'th node
+and an integer 'k'. a valid split of the tree is obtained by removing any set
+of edges, possibly empty, from the tree such that the resulting components
+all have values thatare divisible by 'k', where the value of a connected
+component is the sum of the values of its node. return the maximum number of
+components in any valid split
+"""
+
+
+class Solution(object):
+ def maxKDivisibleComponents(self, n, edges, values, k):
+ """
+ :type n: int
+ :type edges: List[List[int]]
+ :type values: List[int]
+ :type k: int
+ :rtype: int
+ """
+ if n < 2:
+ return 1
+ graph, degree = defaultdict(list), [0] * n
+ for a, b in edges:
+ graph[a].append(b)
+ graph[b].append(a)
+ degree[a] += 1
+ degree[b] += 1
+ node_values, cnt = values[:], 0
+ leaf = deque([i for i in range(n) if degree[i] == 1])
+ while leaf:
+ curr = leaf.popleft()
+ degree[curr] -= 1
+ carry = 0
+ if node_values[curr] % k == 0:
+ cnt += 1
+ else:
+ carry = node_values[curr]
+ for n in graph[curr]:
+ if degree[n] == 0:
+ continue
+ degree[n] -= 1
+ node_values[n] += carry
+ if degree[n] == 1:
+ leaf.append(n)
+ return cnt
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.maxKDivisibleComponents(
+ n=5, edges=[[0, 2], [1, 2], [1, 3], [2, 4]], values=[1, 8, 1, 4, 4], k=6
+ )
+ )
+ print(
+ obj.maxKDivisibleComponents(
+ n=7,
+ edges=[[0, 1], [0, 2], [1, 3], [1, 4], [2, 5], [2, 6]],
+ values=[3, 0, 6, 1, 5, 2, 1],
+ k=3,
+ )
+ )