Задача на массивы

2oleg

An array A[1.. n] contains all the integers from 0 to n except one. It would be easy to
determine the missing integer in O(n) time by using an auxiliary array B[0 .. n] to record
which numbers appear in A. In this problem, however, we cannot access an entire integer in A
with a single operation. The elements of A are represented in binary, and the only operation
we can use to access them is "fetch the jth bit of A[i]," which takes constant time.
Show that if we use only this operation, we can still determine the missing integer in O(n)
time.

2oleg

An array A[1.. n] contains all the integers from 0 to n except one. It would be easy to
determine the missing integer in O(n) time by using an auxiliary array B[0 .. n] to record
which numbers appear in A. In this problem, however, we cannot access an entire integer in A
with a single operation. The elements of A are represented in binary, and the only operation
we can use to access them is "fetch the jth bit of A[i]," which takes constant time.
Show that if we use only this operation, we can still determine the missing integer in O(n)
time.

galka1

You can determinate the missing integer in the time O(k*n where k - the number of the bits, used for the coding of the each integer, and only one additional variable is needed. It's very simple algorithm, so you must think it youself.
и кроме того, если есть дополнительная информация про n, то может быть даже не придется считывать все биты для всех чисел.

Kraft1

The first algorithm, that is with aux. array -- could you describe it in formulas including O(n)?

2oleg

it 's not accepted solution.
O(k*n) ~ O (n log n) because k = log n.

2oleg

the first algorithm:
int s=0;
for(int i=0;i<n;i++) s+=a[i];
printf("the missing is %d\n", (n*(n-1)/2) -s);

Funny

Obviously, to determine the missing number we have to fetch all the bits.
There is O(n*log(n of them, so this problem looks fishy.

galka1

I can do it in O(2*n) operation of "fetch the jth bit of A[i]"
you must determinate which bits are absent

Petrovich40

there's no auxiliary array in the algorithm u've presented. what's wrong about such a solution?

2oleg

O(2*n) is ok. can u show details of your solution?

2oleg

the solution with au array:
memset(b, 0, (n+1)*sizeof(int;
for(int i=0;i<n;i++)b[a[i]]=1;
int res;
for(int i=0;i<=n;i++)if(b[i]==0)res=i;
printf("the missing is %d\n", res);

2oleg

to:
the problem is extracted from "Introduction to algorithms"
Thomas H. Cormen
Charles E. Leiserson
Ronald L. Rivest
Clifford Stein
The MIT Press
the problem is on page 80.

1sandra

I can determine it in any positive (or 0) number of operations :-
'cause it's one!
kiddind a bit :-

1sandra

It's also easy... If you're using n bits to store data...

Funny

I see.
The only possible explanation I can think of is that a ceiling for log2(n) is known a priori (then fixed-length data chunks are used for number representation).
In that case a success of both strategies you've mentioned is clear.

_mrz

Obviously, to determine the missing number we have to fetch all the bits.
There is O(n*log(n of them, so this problem looks fishy.
obviously this is not true
if we have the ability to store the index in the auxilary arrays B[(n+1)/2], C[(n+1)/2] in constant time then I know the algorithm that works in O(n)

Funny

What kind of index do you mean?
Suppose we have alg which finds the missing number without any fetching the jth bit of some A[i]. There is such n that two numbers K and L which differ only in their jth bit exist. We can take two different sequences of numbers: one with A[i]=K and missing L and another one with A[i]=L and missing K. The alg will be unable to distinguish the difference.

Funny

Is it possible the array is sorted in any way?

_mrz

What kind of index do you mean?
Of course I mean the index we use to access array A.
obviously its size in bits is O(log2(n (because array A has n elements) so if we can store/read such numbers to/from the auxiliary arrays in constant time (as we can access the bit in constant time by using logarithmic-sized index) then I know the correct algorithm.
e.g. if RAM operations is fast (as usual in generic hardware) but array A is a kind of very slow storage with per-bit access (or bit access operation is some kind of tricky constant time calculation by some tricky algorithm).
Suppose we have alg which finds the missing number without any fetching the jth bit of some A[i]. There is such n that two numbers K and L which differ only in their jth bit exist. We can take two different sequences of numbers: one with A[i]=K and missing L and another one with A[i]=L and missing K. The alg will be unable to distinguish the difference.
your "alg will be unable to distinguish the difference" may be
obviously your "proof" is wrong because you assume that before algorithm starts you already know the position of bit we don't access which is of course not true (e.g. if we know the lower bit is 0 then we don't have to fetch other bits of those elements in array A[1..n] that has lower bit 1 - after that you may guess the correct algorithm by yourself).
to make all things clear I can just write the algorithm

_mrz

Is it possible the array is sorted in any way?
there's nothing about this stated in our problem so the answer is obviously NO

Funny

You are absolutely right. The thing is clear after some effort

_mrz

ты что матан никогда не учил?
O(2*n) - это тоже самое, что O(n)
функция g(x) относится к классу O(f(x если существует константа C,
такая что для любого x из области определения g:
abs(g(x<=C*abs(f(x
кстати задача действительно решается без проблем с не более чем 2*n+[log2(n)]+1 доступами к единичным битам
т.е. за время O(n)

_mrz

An array A[1.. n] contains all the integers from 0 to n except one. It would be easy to
determine the missing integer in O(n) time by using an auxiliary array B[0 .. n] to record
which numbers appear in A. In this problem, however, we cannot access an entire integer in A
with a single operation. The elements of A are represented in binary, and the only operation
we can use to access them is "fetch the jth bit of A[i]," which takes constant time.
Show that if we use only this operation, we can still determine the missing integer in O(n)
time.
So I can post the algorithm that uses not more than 2*n bit accesses if you still need it.
Оставить комментарий
Имя или ник:
Комментарий: