@Dave : yeah sorry its O(n) where n is number of nodes.
yeah as i said before its a nice approach...
On Tue, Feb 28, 2012 at 10:15 AM, Dave <dave_and_da...@juno.com> wrote:
> @Atul: I don't have an n in my algorithm, so I'm not sure what your
> assessment that my algorithm is O(n^2) means. My algorithm is O(h^2),
> where h is the height of the triangle of cups, but the number of cups
> is n = h(h+1)/2, which is O(h^2), so my algorithm is O(n), as is
> yours.
>
> You'll have to admit that my data structure, an array, is simpler than
> your graph.
>
> Dave
>
> On Feb 27, 10:09 pm, atul anand <atul.87fri...@gmail.com> wrote:
> > @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 algogeeks@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 algogeeks@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.
