 |
dtmoore wrote:
> Willem wrote:
> > dtmoore wrote:
> > ) 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.
> >
> > Hmm, suppose there were three integers missing..
> > Then at the first pass, we get a sum of three integers, s = a + b +
> c.
> >
> > They can't all be larger than s/3, nor can they all be smaller than
> s/3.
>
> Ok so far ...
>
> > So either there is one smaller, or there is one larger.
>
> or both, if a==s/3 .. but I see where you are going
>
> > To find out which, count how many there are smaller than s/3.
> > At the same time make two sums, one of the values below s/3 and the
> > other of those above s/3.
> >
> > So now you know one value, and the sum of the two others.
> > This means you need one more pass to find the values.
>
> Two more passes actually, since you need to apply my "two-value" algo
> to separate the paired values within the appropriate range.
>
> You also need to keep track of the elements larger than s/3, so that
> you can identify the case when a==s/3.
>
> > Still not a generic x-missing solution though.
>
> Actually, this leads the way to a generic solution. The combination
of
> summing and counting elements in a certain range in order to
eliminate
> some of the missing values is generally applicable. The basic
approach
> for the general problem with m missing values is as follows:
>
> Start by summing the array to find the sum of the missing elements,
as
> we have been doing. Then run through array, keeping a count and sum
of
> the elements in m non-overlapping ranges defined as:
>
> e>=(s/2); (s/2)>e>=(s/3); ... ; (s/(m-1))>e>=(s/m); (s/m)>e
>
> None of these ranges can contain *all* of the missing values, so this
> will always suceed in partitioning the missing values into smaller
> ranges.
Actually this can be significantly simplified ... it is also true that
neither of the ranges:
e>(s/m) and e<=(s/m)
can contain all of the missing values. This will significantly
simplify the coding of the algo, since only one condition needs to be
checked on each pass through the array. OTOH, it will also require
more passes through the array, but the final number is still dependent
only on m (and not n), as required in the original specification.
There is a speed vs. space/complexity trade-off here ... but I would
definitely tend to go with the version above for the sake of
simplicity.
Dave Moore
|
|
