Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

@Anshu looks interesting. A few things - >> To check the particular number square can be written as sum of two squares or not. If it has any prime factor x such that x % 4 == 1 then only. - What would be the complexity of finding prime factors. Did you factor in it in overall complexity.

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

@Ravindra To check the particular number square can be written as sum of two squares or not. If it has any prime factor x such that x % 4 == 1 then only. Now about time complexity. suppose u have given array is. 10 6 13 9 17 4 18 12 1 5. now u can easily skip the numbers(1, 4, 6, 9, 12, 18);

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

Sorry.. this is good one, but works for consecutive numbers only from 1..N -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/07wiKGP2WusJ. To post to this g

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

@Anshu >> first check that particular number can be written as the sum of two squares or not What would be the way to figure it out. >> O(n * (number of side which is largest one for any triplet)) Didn't get it. Thanks, - Ravindra On Wed, Oct 19, 2011 at 11:09 AM, anshu mishra wrote: > @Ravind

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

@Ravindra may be the interviewer wants from u that instead of blindly checking for every number. first check that particular number can be written as the sum of two squares or not if yes than only search for that number. So the order will be decrease from O(n^2) to O(n * (number of side which is la

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

@Shashank ..+1 ..I wud say he must be given a tuning award :D :D for solving such eternal conundrum ;) On Mon, Oct 17, 2011 at 2:37 PM, WgpShashank wrote: > @wladimir , its PPT (Pythagoras triplets ) but its number theory based > approach http://en.wikipedia.org/wiki/Pythagorean_triple might

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

*Turing :P On Mon, Oct 17, 2011 at 3:51 PM, Ankur Garg wrote: > @Shashank ..+1 ..I wud say he must be given a tuning award :D :D for > solving such eternal conundrum ;) > > > > On Mon, Oct 17, 2011 at 2:37 PM, WgpShashank > wrote: > >> @wladimir , its PPT (Pythagoras triplets ) but its number

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

@wladimir , its PPT (Pythagoras triplets ) but its number theory based approach http://en.wikipedia.org/wiki/Pythagorean_triple might not be good idea Here is approach : * * *Euclid's formula*[1] is a fundamental formula for genera

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

This appears to be n^(3/2) complexity, looking at one of the solutions in http://stackoverflow.com/questions/575117/pythagorean-triplets assuming elements as sorted. (x cannot be greater than sqrt(2z) as x2+y2 = z2 --> for the worst value of y2 --> 2x^2 = z2 MaxX = ( 2 * N - 1 ) ** 0.5 for x

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

http://stackoverflow.com/questions/575117/pythagorean-triplets Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Fri, Oct 14, 2011 at 3:14 PM, Ankur Garg wrote: > @Rahul > > Pls elaborate with an example ... > > > On Fri, Oct 14, 2011 at 2:35 PM,

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

@rahul It still will be O(n^2) time complexity On 14 October 2011 15:14, Ankur Garg wrote: > @Rahul > > Pls elaborate with an example ... > > > On Fri, Oct 14, 2011 at 2:35 PM, rahul patil < > rahul.deshmukhpa...@gmail.com> wrote: > >> You can take advantage of a basic property of triagle that >

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

suppose sorted array is 1,2,3,5,10,12,13,17,19,25 so if u want to find possible combinations, with 25 as hypotenuse, then only range 10 ... 19 could have answer as 19 + 10 > 25 On Fri, Oct 14, 2011 at 3:14 PM, Ankur Garg wrote: > @Rahul > > Pls elaborate with an example ... > > > On Fri, Oct

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

using properties of tiangle wont help i guess. the will give the range of VALUES you want to restrict yourself to. not the range of INDEX's of the array... On Fri, Oct 14, 2011 at 3:14 PM, Ankur Garg wrote: > @Rahul > Pls elaborate with an example ... > > On Fri, Oct 14, 2011 at 2:35 PM, rahul pa

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

@Rahul Pls elaborate with an example ... On Fri, Oct 14, 2011 at 2:35 PM, rahul patil wrote: > You can take advantage of a basic property of triagle that > > sum of largest side of triangle < sum of other two sides, > > After sorting you could easily deside the range in which possible solution >

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

You can take advantage of a basic property of triagle that sum of largest side of triangle < sum of other two sides, After sorting you could easily deside the range in which possible solution could be found for a chosen hypotenuse On Fri, Oct 14, 2011 at 11:10 AM, ravindra patel wrote: > @Wladi

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

@Wladimir, yeah I have heard about that. Another way of populating primitive pythagoreans is, for any natural number m > 1 (m^2 - 1, 2m, m^2 + 1) forms a pythagorean triplet. This is useful in populating pythagorean tiplets but here the problem is to search such triplets from a given int array. @

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

@rahul...How do u choose z and x for computing z^2 -x^2 ? On Thu, Oct 13, 2011 at 11:34 PM, rahul wrote: > You can create a hash with sqrt(z2-x2). This will make it o(n). The > interviewer just made it lil tricky. That's all > > -- > You received this message because you are subscribed to the Go

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

BTW can we solve this by hashing..That is the only feasible solution which comes to my mind to reduce the time complexity ? On Thu, Oct 13, 2011 at 11:20 PM, Ankur Garg wrote: > Dude this is nothing but 3 sum problem > > http://en.wikipedia.org/wiki/3SUM > > Ask interviewer to check this link an

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

N2 would me minimum On 13-Oct-2011 11:08 PM, "ravindra patel" wrote: > Hi, > Another question I faced in Amazon F2F. > > Given an unsorted array of integers, find all triplets that satisfy x^2 + > y^2 = z^2. > > For example if given array is - 1, 3, 7, 5, 4, 12, 13 > The answer should be - >

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

Dude this is nothing but 3 sum problem http://en.wikipedia.org/wiki/3SUM Ask interviewer to check this link and say he has gone mad!! :P Regards Ankur On Thu, Oct 13, 2011 at 10:29 PM, ravindra patel wrote: > Hi, > Another question I faced in Amazon F2F. > > Given an unsorted array of inte

Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array

I thinking in this property but i dont know how to use :( Euclid, in his book Elements, demonstrated that there is a infinnity of suits early Pythagoreans. Moreover, he found a formula that generates all primitive Pythagorean suits. Given two natural numbers m> n, the suit (a, b, c), where: