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

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.

и кроме того, если есть дополнительная информация про n, то может быть даже не придется считывать все биты для всех чисел.

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

O(k*n) ~ O (n log n) because k = log n.

int s=0;

for(int i=0;i<n;i++) s+=a[i];

printf("the missing is %d\n", (n*(n-1)/2) -s);

There is O(n*log(n of them, so this problem looks fishy.

you must determinate which bits are absent

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

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

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);

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.

'cause it's one!

kiddind a bit :-

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

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.

Obviously, to determine the missing number we have to fetch all the bits.obviously this is not true

There is O(n*log(n of them, so this problem looks fishy.

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)

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.

Is it possible the array is sorted in any way?

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

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

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

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)

An array A[1.. n] contains all the integers from 0 to n except one. It would be easy toSo I can post the algorithm that uses not more than 2*n bit accesses if you still need it.

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 todetermine 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.