[algogeeks] Re: find triplets in an integer array A[] which satisfy condition: a[i]^2 + a[j]^2 = a[k]^2
Algo
loop down array find 2 elements such that c= sqrt(a*a + b*b)
compare if( c*c ==a*a+b*b) //can be optimized we can leave this line
just writing fro clarification if yes prints all the combination
For This I Have A Gud Working Solution which has time complexity of
O(n^2)
Lets genralize this question fro some k say k=100 means we wants to
find out all triplets which is less then kth (here 100) number
so
int n=100;
void doit()
{
int n2 = n*n;
int count = 0;
for (int a=0; a=n; ++a)
for (int b=a; b=n a*a+b*b=n2;++b)
{
int c = (int) Math.sqrt(a*a + b*b);
if (c*c == a*a + b*b)
{
printf(( + a + , + b + , + c +
) );
count++;
}
}
printf(There are + count + combinations.);
}
In Case of Array we need to put a[i] e.g. array elements for which we
need to find out triplets that is also On^n)
solution .Optimization with Others are welcomes.
But this algo will works fine. will not led any error.
Please Write Comment if Anything Wrong with above program or how we
can improve optimize it..because after analyzing u will find that so
many steps
unnecessary calculated ..although we don't want that...
Thanks Regards
Shashank Mani don't B evil U Can Earn While U Learn
--
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.
[algogeeks] Re: find triplets in an integer array A[] which satisfy condition: a[i]^2 + a[j]^2 = a[k]^2
@Fenghuang: No. You don't have to search for b for every a, or more precisely, you don't have to search for a j for every i. Something like this should work for step 3: i = 0 j = k-1 repeat while i = j if asq[i] + asq[j] asq[k] then i = i+1 else if asq[i] + asq[j] asq[k] then j = j-1 else break end repeat if i = j then you have found an i, j, and k satisfying the desired relationship; otherwise, no such i and j exist for this k. This loop is O(n). Surround this with a loop over k and precede that loop with a sort to get Senthilnathan's algorithm. So, as he says, the whole task is O(n log n + n^2) = O(n^2). Dave On Dec 1, 10:11 am, fenghuang fenghaungyuyi...@gmail.com wrote: should it be O(n^2*lgn)? for each x in n, it's O(n), and for each a, it'sO(n), and searching b, it's O(lgn), so it's O(n*n*lgn),Thank You! On Wed, Dec 1, 2010 at 11:02 PM, Senthilnathan Maadasamy senthilnathan.maadas...@gmail.com wrote: Hi, How about the following approach? Step 1: Replace each array element with its square - O(n) Step 2: Sort the array - O(n*log(n)) Step 3: For each element x in the array Find two elements a, b in the array (if any) such that a+b = x. Since finding two such elements can be done in O(n) time in a sorted array, the complexity of this step 3 is O(n^2). While reporting the output you can take the square root and print it out. Total complexity is 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Re: find triplets in an integer array A[] which satisfy condition: a[i]^2 + a[j]^2 = a[k]^2
I have a O(n^2) solution.. Hash all the squares.0(n) Now for every pair find the sum, see if its there in the hash table.O(n^2) Total complexity : O(n^2) On Wed, Dec 1, 2010 at 11:00 PM, fenghuang fenghaungyuyi...@gmail.comwrote: yeah, you're right. thank you and is it the optimal solution about this question? On Thu, Dec 2, 2010 at 1:08 AM, Dave dave_and_da...@juno.com wrote: @Fenghuang: No. You don't have to search for b for every a, or more precisely, you don't have to search for a j for every i. Something like this should work for step 3: i = 0 j = k-1 repeat while i = j if asq[i] + asq[j] asq[k] then i = i+1 else if asq[i] + asq[j] asq[k] then j = j-1 else break end repeat if i = j then you have found an i, j, and k satisfying the desired relationship; otherwise, no such i and j exist for this k. This loop is O(n). Surround this with a loop over k and precede that loop with a sort to get Senthilnathan's algorithm. So, as he says, the whole task is O(n log n + n^2) = O(n^2). Dave On Dec 1, 10:11 am, fenghuang fenghaungyuyi...@gmail.com wrote: should it be O(n^2*lgn)? for each x in n, it's O(n), and for each a, it'sO(n), and searching b, it's O(lgn), so it's O(n*n*lgn),Thank You! On Wed, Dec 1, 2010 at 11:02 PM, Senthilnathan Maadasamy senthilnathan.maadas...@gmail.com wrote: Hi, How about the following approach? Step 1: Replace each array element with its square - O(n) Step 2: Sort the array - O(n*log(n)) Step 3: For each element x in the array Find two elements a, b in the array (if any) such that a+b = x. Since finding two such elements can be done in O(n) time in a sorted array, the complexity of this step 3 is O(n^2). While reporting the output you can take the square root and print it out. Total complexity is 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
