Re: array Puzzle (spoiler)

From: dtmoore (dtmoore_at_rijnh.nl)
Date: 01/23/05 

Date: 23 Jan 2005 14:26:06 -0800

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 <g>, 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. We can then continue to apply this scheme (comparing the
actual sum over a range with its expected value), to any ranges
containing more than one value until they are all eliminated.

Note that the sum of k consecutive integers from p to q is still
"known" ... it is (p+q)*k/2

Note also that the algorithm still qualifies as having O(n) efficiency,
since the number of passes scales only with m.

If I will have time I will code this up and test it ... it would be
cute to do it using a recursive algo ... but in any case I am pretty
sure it is correct.

Dave Moore

Relevant Pages

  • Re: Finding Repeated and Missing Numbers
    ... That said, there is missing information. ... If array one has ... to hold the result without overflow (since as you noted the sum is ... Reading email is like searching for food in the garbage, ...
    (comp.lang.c)
  • Re: Finding Repeated and Missing Numbers
    ... missing = sum - Sum; ... How would you find the only missing element in that array? ... > think of a way to do it while iterating through the array only once. ... can't overflow. ...
    (comp.lang.c)
  • Re: how to find missing value.
    ... then missing number,n = Sum of N natural numbers + Sum of the numbers in Array A. ... the set of numbers would be consecutive if it were sorted, with the exception of the missing number. ...
    (perl.beginners)
  • Re: array Puzzle (spoiler)
    ... >> So now you know one value, and the sum of the two others. ... > some of the missing values is generally applicable. ... > Start by summing the array to find the sum of the missing elements, ... simplify the coding of the algo, since only one condition needs to be ...
    (comp.programming)
  • arraylist.ToArray convert to excel.range() problem
    ... I am creating a function that finds ranges and returns an array with ... all ranges found. ... See the note at the bottom of the procedure. ... There is something I am missing here. ...
    (microsoft.public.dotnet.framework.interop)