Children And Chocolates

The basic idea is to find the number of connected components in the graph. We need to find the total sum of chocolates present in a connected component with their number of children to get the number of children present in the connected component with their total sum of chocolates present. We then need to find the maximum number of children whose sum of chocolates is smaller than equal to ‘C’.
 

Here is the algorithm :
 

1. Create a graph (say, ‘GRAPH’) using the ‘FRIENDS’ array in the form of an adjacency list. (An array of lists in which ‘arr[i]’ represents the lists of vertices adjacent to the ‘ith’ vertex).
2. Push the edges in the ‘GRAPH’.
3. Create an array (say, ‘VISITED’) which will be used to mark all the visited vertices and initialize it with ‘FALSE’ for every vertex present in the ‘GRAPH’.
4. Create a variable (say, ‘RES’) to store the count of maximum children.
5. Call the ‘DFS’ function, DFS(‘GRAPH’, ‘U’, ‘VISITED’, ‘CHOCOLATES’) for every unvisited vertex to count for the number of connected components. where ‘U’ is an unvisited vertex and store its result in a variable (say, ‘TEMP’).
   1. Store ‘TEMP’ and number of children in that connected component in arrays (say ‘COUNT’ and ‘CHILDREN’ respectively).
   2. Call the HELPER(‘C’, ‘COUNT’, ‘CHILDREN’) to find the maximum number of children whose sum of chocolates is smaller than ‘C’.
6. Finally, return the value returned by the HELPER function.

DFS(‘GRAPH’, ‘U’, ‘VISITED’, ‘CHOCOLATES’)

1. Mark ‘U’ as visited in the ‘VISITED’ array.
2. Iterate over all the adjacent vertices of the ‘U’ (say, iterator ‘V’).
   • If ‘VISITED[GRAPH[U][V]]’ is equal to ‘FALSE’
     • Update ‘VISITED[GRAPH[U][V]]’ as 1.
     • Call DFS on all adjacent vertices of ‘U’ while adding the chocolates of each friend.

HELPER function finds the maximum number of children that can get chocolates from the shop. For each value of ‘CHILDREN’, we have two options: whether to include the current value or not. So, we can obtain the maximum count by:

1. Maximum count obtained by ‘N’ - 1 childrens, and ‘C’ chocolates (exclude ‘Nth’ children)
2. Value of ‘Nth’ child plus the maximum value obtained by ‘N’ - 1 childrens and ‘C’ minus the chocolate required by a current number of childrens. ( include ‘Nth’ child)
    

HELPER(‘C’, ‘COUNT’, ‘CHILDREN’, ‘S’)  (where ‘N’ is the size of the ‘COUNT’ array).

1. Base case
   • If ‘C’ or ‘S’  is equal to 0, return 0.
2. Check if ‘COUNT[S - 1] is greater than ‘C’
   • Call the HELPER function by not including the current children.
3. Else
   • Call the HELPER function two times by including the current children and not including the current children and return the maximum value.

O(2^N), where ‘N’ is the number of children.
 

The total number of recursive calls for a vertex can be maximum up to N in which we will traverse every vertex and edge. The total number of vertices is ‘N’, and the total number of edges is ‘M’. For each connected component, we have two choices whether to include or not, which give a 2^N number of options. Therefore, the overall time complexity will be O(2^N).

O(N + M), where ‘N’ is the number of children, and ‘M’ is the number of connections between friends.

For each vertex, we store its adjacent vertices; therefore, storing them in the form of a graph will require O(N + M) space. We also use the ‘VISITED’ array, which all require O(N) space. The recursive stack of the DFS function will contain all the neighbors of a vertex, which at most can be ‘N’ vertices. Recursion stack for HELPER function can have at most ‘N’ number of calls. Therefore, the overall space complexity will be O(N + M).