wont it be additional overhead to sum again from S/2+1 to n+2.instead subtract from s the number we got ???
On Tue, Aug 4, 2009 at 9:21 PM, sharad kumar <aryansmit3...@gmail.com>wrote: > after getting one number cant u subtract from S?? > > On Tue, Aug 4, 2009 at 5:53 PM, Anil C R <cr.a...@gmail.com> wrote: > >> Pretty! :) >> >> Channa Bankapur wrote: >> > Elegant.. I think it can't be better than this. Identifying that each >> > of them are on different sides of S/2 was the key! >> > >> > >> > On Tue, Aug 4, 2009 at 10:05 AM, Prunthaban Kanthakumar >> > <pruntha...@gmail.com <mailto:pruntha...@gmail.com>> wrote: >> > >> > Here is the right answer: >> > >> > Find the sum of missing numbers. Call it S (this is a easy to do). >> > Now the two missing numbers are such that one is <=S/2 and the >> > other is > S/2 >> > Have two variables S1 and S2, traverse the array and add >> > everything <= S/2 to S1 and > S/2 to S2. >> > Now >> > First number = (Sum of numbers from 1 to S/2) - S1 >> > Second Number = (Sum of numbers from [S/2 + 1] to n+2) - S2 >> > >> > O(n) time and O(1) space. >> > >> > >> > On Tue, Aug 4, 2009 at 3:28 AM, Karthik Singaram Lakshmanan >> > <karthiksinga...@gmail.com <mailto:karthiksinga...@gmail.com>> >> wrote: >> > >> > >> > well..will this work? >> > >> > x + y = SUM(1:N+2) - SUM(array) = a >> > x^2 + y^2 = SUM(1^2:(N+2)^2) - SUM(array.^2) = b >> > so (a^2 - b) = 2xy >> > >> > so xy = (a^2-b)/2 = k (say) >> > >> > now, >> > >> > x + (k/x) = a >> > >> > x^2 + k = ax >> > (x, y) = (a +/- sqrt(a^2-4k))/2 >> > >> > I may not have written the equations correctly (need coffee !!!) >> > but you get the general idea... >> > solve a quadratic equation to solve for (x+y) = a and (x^2 + >> > y^2) = b >> > >> > - Karthik >> > >> > >> > >> > >> > >> > >> > >> > > >> >> >> >> >> > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
