|
|
 | | From: | dtmoore | | Subject: | Re: array Puzzle (spoiler) | | Date: | 23 Jan 2005 04:52:30 -0800 |
|
|
 |
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.
How would you do it using roots?
> If so, I don't think that generalizes very well (it seems to go in
the
> direction of the knapsack problem),
I don't think "my" algorithm generalizes very well either, but I can
imagine that there are some more advanced number theory tricks that can
be used to determine conditions that can be checked to find any number
of missing values. The main question is whether the number of required
passes through the input array scales with n, in which case the O(n)
time efficiency requirement would fail to be met.
My intuition is that, for m missing values, the time to find them
scales as some function of m (thus still satisfying the problem
conditions), but I can't prove it.
> but perhaps some mathematical mind
> here could shed more light on that issue.
>
Agreed .. *HELP* .. 8*)
Dave Moore
|
|
| | From: | Alf P. Steinbach | | Subject: | Re: array Puzzle (spoiler) | | Date: | Sun, 23 Jan 2005 13:17:26 GMT |
|
|
| * 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.
>
> 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.
But hey, even though your solution is much more elegant and not
to mention that it's also much more realistic, remember that I just saw
the OP's post and then _immediately_ sent it over here! ;-)
[snip]
> > but perhaps some mathematical mind
> > here could shed more light on that [more than 2 values
> > missing] issue.
> >
>
> Agreed .. *HELP* .. 8*)
--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
|
|
| | From: | Willem | | Subject: | Re: array Puzzle (spoiler) | | Date: | Sun, 23 Jan 2005 14:05:34 +0000 (UTC) |
|
|
| 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.
So either there is one smaller, or there is one larger.
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.
Still not a generic x-missing solution though.
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
|
|
| | From: | Bill Godfrey | | Subject: | Re: array Puzzle (spoiler) | | Date: | 23 Jan 2005 20:26:44 GMT |
|
|
| Willem wrote:
> Still not a generic x-missing solution though.
Oh okay then. Here's my one that requires the original array to be
modifiable. (Which is really just a cheat to get around the O(1) extra
memory use restriction.)
First pass, for each item...
If it is a non-zero, move it to its original position in the array, before
it was shuffled, swapping with the item found there. (Be careful about
swapping when an item is already in place.)
This will result in a sorted array with the zeros in the place of the
missing items.
Second pass, for each item...
If it is zero, you have a missing number. Its position in the array is the
missing number itself.
This should work for any M (missing numbers) from 0 to N.
Bill, cheater!
--
http://billpg.me.uk/
usenet(at)billpg(dot)me(dot)uk
|
|
|
