@DEV,your idea is nice.....but i think it wont work in case the array is having repeated elements....am i right????
On Wed, Dec 1, 2010 at 1:51 PM, nishaanth <nishaant...@gmail.com> wrote: > 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<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Anoop Chaurasiya CSE (2008-2012) NIT DGP -- 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.
