|
|
 | | From: | dtmoore | | Subject: | Re: array Puzzle (spoiler) | | 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 , 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
|
|
| | From: | Willem | | Subject: | Re: array Puzzle (spoiler) | | Date: | Mon, 24 Jan 2005 00:15:13 +0000 (UTC) |
|
|
| dtmoore wrote:
) Willem wrote:
)> 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
When I say 'larger' I actually mean 'equal or larger'. Sorry.
That makes stuff a lot easier.
)> 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 already know the sum of the two others, so you only need the second
pass of your algorithm.
) You also need to keep track of the elements larger than s/3, so that
) you can identify the case when a==s/3.
See above, the bit about 'larger' meaning 'equal or larger'.
SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
|
|
|
