@ pacific:
Also consider the choice of flipping the node itself.
And if an internal node cannot be flipped, it is still possible to flip
its value, only the above choice is not taken into consideration..
On 2010-12-28 13:27, pacific pacific 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
<mailto: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
<mailto: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
algogeeks@googlegroups.com <mailto:algogeeks@googlegroups.com>.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
<mailto: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 algogeeks@googlegroups.com
<mailto:algogeeks@googlegroups.com>.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
<mailto: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.
--
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.
