I have a tree, now I want to count the number of paths going up to the root of the tree, (it need not reach till root node).
While counting the paths, I want to find the cost for that path and do a calculation as (cost % k = 0), to find all such valid paths.
For input k = 2 and list = [1,1,1,1], from = [1,1,4], to = [2,4,3] List represent cost of every node. from and to represent the edges in the tree.
the tree represented as :
For the above tree, we have 8 possible paths:
1
2
4
2->1
4->1
3
3->4 (this has a path that can reach root node, so this path is considered)
3->4->1
But only valid paths are
2->1
4->1
3->4
that have cost % k = 0
so the result is 3.
This is my code, here I am checking from and to edges sum and checking if remainder with k is 0, also checking to edges with the remainder as 0.
public int findValidPaths(List<Integer> list, int nodes, List<Integer> from, List<Integer> to, int k) {
int result = 0;
for(int e : to) {
if(list.get(e-1) % k == 0) {
result ;
}
}
for(int i=0; i<from.size(); i ) {
int cost = list.get(from.get(i)-1) list.get(to.get(i) -1);
if(cost%k == 0) {
result ;
}
}
return result 1;
}
My approach is not correct as I am not checking all paths, how to solve this problem.
constraints:
cost : 1 to 10^9
k : 1 to 10^5
CodePudding user response:
A general O(n)
formulation can be let f(n)
represent all the remainders that can be reached in prefix sums modulo k
of traversals down from the root. Then node n
can be paired with as many of those remainders that are the same as (sum_head n) % k
, where sum_head
is the prefix sum modulo k
ending at n
s parent.
In order to use space efficiently, we can use a map of sum mod k -> count
, recursing down into the tree and unsetting the prefix sum we just created (i.e., backtracking) after the recursion.
For example, k = 3
G(2)
/ \
E(1) F(2)
/ \ / \
A(2) B(4) C(2) D(5)
Prefix sums modulo k = 3
:
G -> E -> A
2 0 2
-> B
1
G -> F -> C
2 1 0
-> D
0
We arrive at E and count the 0 prefix sum there. At A, we match 2 with the 2 in the prefix_sum_mod_k
map, which accounts for the path A -> E
.
We backtrack, unsetting a 2 and examine B, which has no match in the map.
We backtrack to G, unsetting a 1 and a 0, and proceed to F, which has no match. We proceed to C, which is a 0 and count it. We backtrack to F, unsetting a 0, and proceed to D, counting one more 0.
Total: 4
E -> G
A -> E
C -> F -> G
D -> F -> G
CodePudding user response:
For code it is not clear which algorithm you are using for finding paths in tree but depth-first-search can be used to find paths in a graph or tree. https://www.geeksforgeeks.org/find-paths-given-source-destination/