| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
Suppose you are given N random integers p uniformly distributed in the
i
1.5 1.5
range -N .. N . We're interested in finding triples p , p , p such
a b c
1.5
that p + p = p . The expected number of such triples is k�N , for
a b c
1.5 1.5
some k > 1 (verify this). Can N of these triples be found in time O(N )?
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 1569.1 | Some clarification neede. | CADSYS::COOPER | Topher Cooper | Thu Feb 20 1992 17:55 | 5 |
Are we sampling with or without replacement? Do p[a] and p[b] need to
be distinct? How about if the number in question was only drawn once?
How about p[a] and p[c]?
Topher
| |||||
| 1569.2 | CLT::KOBAL::GILBERT | Ownership Obligates | Fri Feb 21 1992 14:55 | 34 | |
The N given integers are distinct (I should've said so in .0). They
aren't being *sampled*, they're just *input* to the requested algorithm.
The distribution is given because the desired algorithm might only run
in 'expected' time O(N^1.5); this is still useful.
In p[a] + p[b] = p[c], the p[a] and p[b] needn't be distinct. But this offers
fewer than N additional triples -- small beans since the goal is O(N^1.5).
Similarly for p[a] and p[c] being equal.
I'm looking for something like the following O(N�) algorithm, but faster:
for a := 1 to N do
for b := 1 to N do
for c := 1 to N do
if p[a] + p[b] = p[c] then
writeln(p[a], p[b], p[c]);
The following is an O(N�) algorithm:
sort p[1..N] into ascending order
for c := 1 to N do
a := 1; { the p[a] increase }
b := N; { and the p[b] decrease }
while a <= N and b >= 1 do
if p[a] + p[b] = p[c] then
writeln(p[a], p[b], p[c]);
a := a + 1;
b := b - 1;
else if p[a] + p[b] < p[c]
then
a := a + 1;
else
b := b - 1;
| |||||