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.com>wrote: > 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.com<algogeeks%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.com<algogeeks%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.com<algogeeks%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.
