Consider the below e.g
n+2 array is {1,2,3,4}
and given the n array as {3,4} then can you pls explain how ur logic
finds 1,2 as missing?
thanks
On Aug 4, 9:35 am, Prunthaban Kanthakumar <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> 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
-~----------~----~----~----~------~----~------~--~---
