The description on internal nodes indicates this:
The value of an "AND" gate node is given by the logical AND of its TWO
children's values.
The value of an "OR" gate likewise is given by the logical OR of its TWO
children's values.
On 2010-12-28 13:35, suhash wrote:
Your approach is for a binary tree, but the problem statement does not
say anything about it.
On Dec 28, 10:27 am, pacific pacific<pacific4...@gmail.com> wrote:
here is my approach :
Starting from the root node ,
if root node need to have a 1 ...
if root is an and gate :
flips = minflips for left child to have value 1 + minflips for the
right child to have value 1
else
flips = minimum of ( minflips for left child to have value 1 , minflips
for right child to have value 1)
For a leaf node , return 0 if the leaf has the value needed else return
INFINITY.Also if at any internal node if it is not possible return INFINITY.
On Tue, Dec 28, 2010 at 10:06 AM, Anand<anandut2...@gmail.com> wrote:
@Terence.
Could please elaborate your answer. Bottom up level order traversal helps
to get the final root value but how to use it to find minimum flips needed
to Obtain the desired root value.
On Fri, Dec 24, 2010 at 1:56 AM, Terence<technic....@gmail.com> wrote:
Using the same level order traversal (bottom up), calculating the minimum
flips to turn each internal node to given value (0/1).
On 2010-12-24 17:19, bittu wrote:
Boolean tree problem:
Each leaf node has a boolean value associated with it, 1 or 0. In
addition, each interior node has either an "AND" or an "OR" gate
associated with it. The value of an "AND" gate node is given by the
logical AND of its two children's values. The value of an "OR" gate
likewise is given by the logical OR of its two children's values. The
value of all of the leaf nodes will be given as input so that the
value of all nodes can be calculated up the tree.
It's easy to find the actual value at the root using level order
traversal and a stack(internal if used recursion).
Given V as the desired result i.e we want the value calculated at the
root to be V(0 or 1) what is the minimum number of gates flip i.e. AND
to OR or OR to AND be required at internal nodes to achieve that?
Also for each internal node you have boolean associated which tells
whether the node can be flipped or not. You are not supposed to flip a
non flippable internal node.
Regards
Shashank Mani Narayan
BIT Mesra
--
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<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.
