write a recursive function getmin(node, value) that returns the least number of flips necessary for the subtree rooted at "node" to give the result "value". recursive relations are easy to come up with, so I leave it as an exercise :)
memorize the values calculated, so, never calculate a result more than once. Since "value" is either 0 or 1, this algorithm works in O(n) time and space complexity where n is the number of nodes. On Tue, Aug 3, 2010 at 11:41 AM, RITESH SRIVASTAV <riteshkumar...@gmail.com>wrote: > level of the tree is given or not ? > and where do we have to output V , just at the node we get it or at > the root ? > > On Aug 3, 1:56 pm, jalaj jaiswal <jalaj.jaiswa...@gmail.com> wrote: > > given a complete binary tree (either a node is a leaf node or has two > > children) > > every leaf node has value 0 or 1. > > every internal node has value as the AND gate or OR gate. > > you are given with the tree and a value V. > > you have to output the minimum number of flips (AND to OR or OR to AND) > if > > the evaluated value is not equal to V, if it is equal return 0, if not > > possible return -1. > > you can just change the value of internal nodes i.e can make and to or , > or > > to and to get the desired output > > give the minimum number of flips required to get the desired output. > > > > -- > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
