Hi all, recently in an interview i have the following question.
you are given a tree rooted at 1, with N vertices .Each vertex has a value associated with it. The value of the ith vertex is ai. consider fi as the aith beatutiful number.A beautiful number is a positive number whose sum of the square digits is less than or equal to X.
You have to process M queries where each query can be.
1. 1 i y : update ai with y
2. 2 i : output the sum of fi for all the nodes of sub-tree of node i(including node i)
output your ans modulo 10^9+7
Input format 1. N,M,X where N is number of vertices,M no of queries, X is a constant 2. Next N-1 lines will be two vertices which are connected to each other. 3. then you will have M queries.
Constraints 1<=N,M,i,y<=10^5 1<X<10^10
My Approach 1.Created an adjacency list to contain the graph structure of the tree. O(edges)
From that adjacency list created a tree structure. O(n)
if the query is of type 1, replaced that value of node. O(1)
else go to that node, and find maximum among its children& itself. O(n)
Find the starting max beautiful numbers. O(max)
compute the desired sum. O(n)
total complexity O(n+max).
what will be your approach?How i can improve mine?
