 | Alf P. Steinbach wrote:
> * dtmoore:
> > Alf P. Steinbach wrote:
> > > * dtmoore:
> > > > Alf P. Steinbach wrote:
> > > > > * puzzlecracker:
> > > > > > Given an array of size n and populated with consecutive
> > > > > > integers from 1 to n i.e. [1, 2...n-1, n] in random order.
> > > > > > Two integers are removed, meaning zero is placed in their
> > > > > > places. Give O (n) efficient algorithm to find them?
> > > >
> > > > [Snip}
> > > >
> > > > > As a programming puzzle it's a bit more interesting (but
> > > > > still novice-level) if memory usage is restricted to O(1)
> > > > > except the original array itself, and for that I'm cross-
> > > > > posting this to [comp.programming], with follow-up there.
> > > >
> > > > Ok, I can see how to solve the puzzle with an algorithm that is
> > > > O(n) in time and O(1) in memory, but only when two values are
> > > > removed. Is there to solve it when more than two values are
> > > > zero'd out and still use O(1) memory?
> > >
> > > Well I don't know.
> > >
> > > I assume your solution involves a root?
> >
> > Actually no, I guess it is simpler than that. Since the (before
> > cross-posting) OP's homework is probably past due by now , I
> > will lay out the algorithm here.
> >
> > The key is that the integers in the input array are sequential,
> > even if they are shuffled. Thus the sum, S, of the complete,
> > original array is known: S=(n+1)*n/2. So, one can compute the
> > sum, s, of the input array (with the zeros) and subtract it from
> > the expected value to recover the sum of the missing elements
> > (a + b = S - s = c).
> >
> > Since a and b are unique, one of them must be smaller than c/2.
> > So, we again iterate through the array, this time summing only
> > those elements which are less than c/2, and again subtract from
> > the expected sum: (k+1)*k/2, where k is the largest integer less
> > than c/2.
> >
> > This will recover the value of the smallest of the two "missing"
> > integers, and of course the second comes from a + b = c.
Very nice! A complete solution that can be implemented
straightforwardly without numerical issues!
> > How would you do it using roots?
>
> It was much more brute force, computing both the sum and the product
> of the numbers (the latter quantity would tend to be, uh, laaarge),
>
> x + y = s
> x * y = p
>
> where s = n*(n+1)/2-sumOfArray and p = n!/productOfArray, yields
> simple quadratic equation.
Actually, using roots is not necessary, since you can iterate through
the possible x and y (again, its O(n)) and just check to see if its
matches the product. The real problem with that solution is computing
n!
But similarly, the following can be computed:
x + y = s
x^2 + y^2 = q
And this solves to a unique pair of x and y as well (exercise to the
reader.) The advantage of this is that it can be computed exactly
with a bignum library that only requires triple-wide integers. Also
there is a chance that computing q (mod k) (instead of q which can
overflow), for some small k might still work, and can be computed as
well. The point is that there is almost surely a fixed sequence of
k's (probably some appropriately chosen primes or something like that)
for which you can compute these q's and again do the forward for loop.
--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
|
|
