|
|
 | | From: | puzzlecracker | | Subject: | riddles array | | Date: | 19 Jan 2005 17:44:55 -0800 |
|
|
 | 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?
|
|
| | From: | Torben_Ęgidius_Mogensen | | Subject: | Re: riddles array | | Date: | 20 Jan 2005 12:05:00 +0100 |
|
|
| "puzzlecracker" writes:
> 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?
sum := 0
for i:= 1 to n do
sum := sum + 2^a[i];
sum := 2^(n+1)-sum;
n1 := floor(log_2(sum));
sum := sum - 2^n1;
n2 := floor(log_2(sum));
n1 and n2 are your missing numbers.
This algorithm assumes constant-time arithmetic on large numbers,
which might not be approriate. You can get around this by using a
second array:
for i:= 1 to n do
b[i] := 0;
for i:= 1 to n do
if a[i]>0 then b[a[i]] := 1;
n1 := 0;
n2 := 0;
for i:= 1 to n do
if b[i] = 0 then
if n1 = 0 then n1 := i else n2 := i
Again, n1 and n2 are your missing numbers.
Torben
|
|
| | From: | sandey | | Subject: | Re: riddles array | | Date: | 20 Jan 2005 04:00:40 -0800 |
|
|
| Cant we do it simply like
A > Maintain another array d[] of size n,d[]=0 at first.
B > Go through the first array in a ascending order, if i is present in
array[j], then
put d[i]=1
C > At the end, go through the array d, and see which ones have d[u] =
0, those are your numbers.
That will take O(n) time and O(n) space. If you dont want an O(n)
space, then u have to think about adding them up, otherwise a simple
algo like one above suffices.
Hope that helps,
Sandeep Dey.
|
|
|
