Amazon Interview Question
Software Engineer / DevelopersCountry: United States
I think u mean the number of solutions is 3*N + 1.
We have 3 ways to choose 1 out of a,b and c as 0 and N values for the other two => 3*N. Furthermore, + 1 because of the solution triplet (0,0,0). :)
Here is my answer to this question. The time complexity of my implementation is O(logN * logN). Can we do better?
basicalgos.blogspot.com/2012/03/30-computer-all-possible-solution-of.html
At the risk of sounding a little rude, no one is interested in seeing code first when they seek a solution to a problem.
Can you please explain the logic, then the code would make a little more sense. Thank you.
By Fermat's last theorem, there are no positive integral solutions to: x^n + y^n = z^n for n>2. Hence, there exist solutions only of the form (0,a,a) and (a,0,a), hence there are totally (2*N + 1) solutions since 'a' belongs to [0,N].
- Anonymous March 25, 2012