I found an error in my solution. -----
A*x + B*y = C If x, y are both no non-negative, it takes (x+y)*2 steps. If one of them is negative, it takes (|x|+|y|)*2-1 steps. //There should be abolute value signs We can iterate x from -max(A, B, C) to max(A, B, C) and get many x-y tuples, each of which denote a solution. The minimum solution is the best. I think the iteration range can be reduce. What is a more effective algorithm? To nikhil garg Suppose A = 5, B = 8, C = 1, we can following step to approach: A B 0 8 //fill B 5 3 //pour water from B to A 0 3 //empty A 3 0 //pour water from B to A 3 8 //fill B 5 6 //pour water from B to A 0 6 5 1 //obtain 1 We can prove we can obtain gcd(A,B), 2 gcd(A,B), 3 gcd(A,B), ... --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
