@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.
