@Gene , @dave : +1 +1 On Tue, Feb 28, 2012 at 10:49 AM, atul anand <[email protected]>wrote:
> @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 <[email protected]> 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 <[email protected]> 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 [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. >> >> > -- 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.
