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); and u have to check only for these numbers(5, 10, 13, 17); so time complexity will reduce to O(n * (number of side which can be largest one for any triplet) ). -- 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?hl=en.
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 anshumishra6...@gmail.comwrote: @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 largest one for any triplet)) and in practical it will be much less compare to 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 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?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 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?hl=en.
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 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?hl=en.
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 largest one for any triplet)) and in practical it will be much less compare to 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 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?hl=en.
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]http://en.wikipedia.org/wiki/Pythagorean_triple#cite_note-0 is a fundamental formula for generating Pythagorean triples given an arbitrary pair of positive integers *m* and *n* with *m* *n*. The formula states that the integers p=m^2-n^2 , q=2mn r=m^2+n^2 , we have to sort the array in non-increasing order , then for each mn we have to generate the all such p,q,r in worst case it will also requires O(N^2) such p,q,r for each MN isn't it ? then its not less then O(n^2) ?? Even with this approach,The triple generated by Euclid's formula is primitive if and only if *m* and *n* are coprime and *m*-*n* is odd. If both *m* and *n* are odd, then *a*, *b*, and *c* will be even, and so the triple will not be primitive; however, dividing *a*, *b*, and *c* by 2 will yield a primitive triple if *m* and *n* are coprime. @all other , its similar to 3 sun , can't be done in less then O(N^2) if number are not in range , When the integers are in the range [-*u* ... *u*], 3SUM can be solved in time O(n + *u* lg *u*) by representing *S* as a bit vector and performing a discrete convolution using FFT. i wondered if any other algo/code/link you have which works in less then O(N^2) , Better if One Explain The Approach or Algorithm , You Might able to fill Patent :D Thanks Shashank CSE, BIT Mesra -- 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/-/JQWWHDKMCiAJ. 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?hl=en.
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 shashank7andr...@gmail.comwrote: @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]http://en.wikipedia.org/wiki/Pythagorean_triple#cite_note-0 is a fundamental formula for generating Pythagorean triples given an arbitrary pair of positive integers *m* and *n* with *m* *n*. The formula states that the integers p=m^2-n^2 , q=2mn r=m^2+n^2 , we have to sort the array in non-increasing order , then for each mn we have to generate the all such p,q,r in worst case it will also requires O(N^2) such p,q,r for each MN isn't it ? then its not less then O(n^2) ?? Even with this approach,The triple generated by Euclid's formula is primitive if and only if *m* and *n* are coprime and *m*-*n* is odd. If both *m* and *n* are odd, then *a*, *b*, and *c* will be even, and so the triple will not be primitive; however, dividing *a*, *b*, and *c* by 2 will yield a primitive triple if *m* and *n* are coprime. @all other , its similar to 3 sun , can't be done in less then O(N^2) if number are not in range , When the integers are in the range [-*u* ... *u*], 3SUM can be solved in time O(n + *u* lg *u*) by representing *S* as a bit vector and performing a discrete convolution using FFT. i wondered if any other algo/code/link you have which works in less then O(N^2) , Better if One Explain The Approach or Algorithm , You Might able to fill Patent :D Thanks Shashank CSE, BIT Mesra -- 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/-/JQWWHDKMCiAJ. 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?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 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?hl=en.
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 in 3..MaxX {
y = x+1
z = y+1
m = x*x + y*y
k = z * z
while z = N {
while k m {
z = z + 1
k = k + (2*z) - 1
}
if k == m and z = N then {
// use x, y, z
}
y = y + 1
m = m + (2 * y) - 1
}
}
--
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/-/UjRPZ8oIbmkJ.
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?hl=en.
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. @ rahul, Hash of z^2 - x^2 for each pair of z,x itself will of the size n*(n-1). I am not sure how it will work in O(n) time then. Thanks, - Ravindra On Fri, Oct 14, 2011 at 12:25 AM, Ankur Garg ankurga...@gmail.com wrote: @rahul...How do u choose z and x for computing z^2 -x^2 ? On Thu, Oct 13, 2011 at 11:34 PM, rahul rahul...@gmail.com 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 Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/2Ge2pjt4N-4J. 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?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 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?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 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?hl=en.
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 ravindra.it...@gmail.comwrote: @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. @ rahul, Hash of z^2 - x^2 for each pair of z,x itself will of the size n*(n-1). I am not sure how it will work in O(n) time then. Thanks, - Ravindra On Fri, Oct 14, 2011 at 12:25 AM, Ankur Garg ankurga...@gmail.com wrote: @rahul...How do u choose z and x for computing z^2 -x^2 ? On Thu, Oct 13, 2011 at 11:34 PM, rahul rahul...@gmail.com 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 Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/2Ge2pjt4N-4J. 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?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 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?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 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?hl=en. -- Regards, Rahul Patil -- 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?hl=en.
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 rahul.deshmukhpa...@gmail.comwrote: 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 ravindra.it...@gmail.com wrote: @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. @ rahul, Hash of z^2 - x^2 for each pair of z,x itself will of the size n*(n-1). I am not sure how it will work in O(n) time then. Thanks, - Ravindra On Fri, Oct 14, 2011 at 12:25 AM, Ankur Garg ankurga...@gmail.comwrote: @rahul...How do u choose z and x for computing z^2 -x^2 ? On Thu, Oct 13, 2011 at 11:34 PM, rahul rahul...@gmail.com 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 Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/2Ge2pjt4N-4J. 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?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 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?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 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?hl=en. -- Regards, Rahul Patil -- 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?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 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?hl=en.
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 ankurga...@gmail.com 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 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 ravindra.it...@gmail.com wrote: @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. @ rahul, Hash of z^2 - x^2 for each pair of z,x itself will of the size n*(n-1). I am not sure how it will work in O(n) time then. Thanks, - Ravindra On Fri, Oct 14, 2011 at 12:25 AM, Ankur Garg ankurga...@gmail.com wrote: @rahul...How do u choose z and x for computing z^2 -x^2 ? On Thu, Oct 13, 2011 at 11:34 PM, rahul rahul...@gmail.com 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 Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/2Ge2pjt4N-4J. 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?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 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?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 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?hl=en. -- Regards, Rahul Patil -- 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?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 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?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 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?hl=en.
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 ankurga...@gmail.com 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 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 ravindra.it...@gmail.com wrote: @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. @ rahul, Hash of z^2 - x^2 for each pair of z,x itself will of the size n*(n-1). I am not sure how it will work in O(n) time then. Thanks, - Ravindra On Fri, Oct 14, 2011 at 12:25 AM, Ankur Garg ankurga...@gmail.comwrote: @rahul...How do u choose z and x for computing z^2 -x^2 ? On Thu, Oct 13, 2011 at 11:34 PM, rahul rahul...@gmail.com 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 Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/2Ge2pjt4N-4J. 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?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 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?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 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?hl=en. -- Regards, Rahul Patil -- 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?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 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?hl=en. -- Regards, Rahul Patil -- 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?hl=en.
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 ankurga...@gmail.com 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 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 ravindra.it...@gmail.com wrote: @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. @ rahul, Hash of z^2 - x^2 for each pair of z,x itself will of the size n*(n-1). I am not sure how it will work in O(n) time then. Thanks, - Ravindra On Fri, Oct 14, 2011 at 12:25 AM, Ankur Garg ankurga...@gmail.comwrote: @rahul...How do u choose z and x for computing z^2 -x^2 ? On Thu, Oct 13, 2011 at 11:34 PM, rahul rahul...@gmail.com 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 Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/2Ge2pjt4N-4J. 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?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 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?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 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?hl=en. -- Regards, Rahul Patil -- 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?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 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?hl=en. -- Bittu Sarkar 5th Year Dual Degree Student Department of Computer Science Engineering Indian Institute of Technology Kharagpur -- 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?hl=en.
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 ankurga...@gmail.com 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 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 ravindra.it...@gmail.com wrote: @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. @ rahul, Hash of z^2 - x^2 for each pair of z,x itself will of the size n*(n-1). I am not sure how it will work in O(n) time then. Thanks, - Ravindra On Fri, Oct 14, 2011 at 12:25 AM, Ankur Garg ankurga...@gmail.comwrote: @rahul...How do u choose z and x for computing z^2 -x^2 ? On Thu, Oct 13, 2011 at 11:34 PM, rahul rahul...@gmail.com 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 Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/2Ge2pjt4N-4J. 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?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 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?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 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?hl=en. -- Regards, Rahul Patil -- 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?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 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?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 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?hl=en.
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: a = m ^ 2 - n ^ 2, b = 2mn, c = m ^ 2 + n ^ 2, Wladimir Araujo Tavares *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/ Homepage http://lia.ufc.br/%7Ewladimir/ | Maratonahttps://sites.google.com/site/quixadamaratona/| * On Thu, Oct 13, 2011 at 1:59 PM, ravindra patel ravindra.it...@gmail.comwrote: 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 - 5, 12, 13 and 3, 4, 5 I suggested below algo with complexity O(n^2) - - Sort the array in descending order. - O(nlogn) - square each element. - O(n) Now it reduces to the problem of finding all triplets(a,b,c) in a sorted array such that a = b+c. The interviewer was insisting on a solution better than O(n^2) which I dont think is feasible, but I couldn't prove that. Anyone has any idea. Thanks, - Ravindra -- 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?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 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?hl=en.
Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array
N2 would me minimum On 13-Oct-2011 11:08 PM, ravindra patel ravindra.it...@gmail.com 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 - 5, 12, 13 and 3, 4, 5 I suggested below algo with complexity O(n^2) - - Sort the array in descending order. - O(nlogn) - square each element. - O(n) Now it reduces to the problem of finding all triplets(a,b,c) in a sorted array such that a = b+c. The interviewer was insisting on a solution better than O(n^2) which I dont think is feasible, but I couldn't prove that. Anyone has any idea. Thanks, - Ravindra -- 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?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 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?hl=en.
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 ankurga...@gmail.com wrote: 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 ravindra.it...@gmail.com 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 - 5, 12, 13 and 3, 4, 5 I suggested below algo with complexity O(n^2) - - Sort the array in descending order. - O(nlogn) - square each element. - O(n) Now it reduces to the problem of finding all triplets(a,b,c) in a sorted array such that a = b+c. The interviewer was insisting on a solution better than O(n^2) which I dont think is feasible, but I couldn't prove that. Anyone has any idea. Thanks, - Ravindra -- 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?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 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?hl=en.
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 ravindra.it...@gmail.comwrote: 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 - 5, 12, 13 and 3, 4, 5 I suggested below algo with complexity O(n^2) - - Sort the array in descending order. - O(nlogn) - square each element. - O(n) Now it reduces to the problem of finding all triplets(a,b,c) in a sorted array such that a = b+c. The interviewer was insisting on a solution better than O(n^2) which I dont think is feasible, but I couldn't prove that. Anyone has any idea. Thanks, - Ravindra -- 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?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 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?hl=en.
