Loading...

algogeeks@googlegroups.com

[Prev] Thread [Next]  |  [Prev] Date [Next]

Re: [algogeeks] Re: google question atul anand Mon Feb 27 20:01:14 2012

@Dave : my code is not that complicated ...if you ignore the helper
function and check fillCup();
it just similar to preorder travesal and pour half to left and right child.

here is the explanation :-

node* fillCup(node *root,float pour,float capacity)
{
float temp;
    if(root==NULL)
        return NULL;

    if(root->data+pour >= capacity)
    {
        if(root->data==0) //  if cup is empty then fill cup to full and
reduce pour value for the next level
        {
            root->data=capacity;
            pour=pour-capacity;
        }
        else
        {
            // if there is alreday some water in the cup , then it will
fill the cup and reduce pour =pour - empty volume in partially filled cup.
            temp=capacity-(root->data);
            root->data=capacity;
            pour=pour-temp;
            if(pour==0)
            {
                return root;
            }

        }
    }
    else
    {
       // this is for the part where overflow will never happen , even
after adding the poured quantity to the cup.
        root->data+=pour;
        return root;

    }

    fillCup(root->left,pour/2,capacity);    // pour 1/2 to the left
    fillCup(root->right,pour/2,capacity); //  pour 1/2 to the right
}

Time complexity = O(n).

your approach is nice but it O(n^2) .

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.