Start with an array A of n+1 entries each consisting of an integer between 1 and n. By the pigeonhole principle there must be some i≠j and a w such that A(i)=A(j)=w. The goal is to find w. Depending on A there may be several such w, we want to find any one of them. The catch is that you only get to use O(log n) bits of memory.
First a warm-up puzzle: Find w using only O(n) queries to entries of A (remember you only get O(log n) space). Hint: Use pointer chasing.
Now suppose A is streamed, that is we get in order A(1),A(2),…,A(n+1) and then get another pass etc. How many passes do you need to find a w?
You can find w in n+1 passes just by trying each possible value for w. With a little work you can use O(log n) passes doing a binary search.
Muthukrishnan asks whether the number of passes needed is Ω(log n) or O(1) or something in between.
"First a warm-up puzzle: Find w using only O(n) queries to entries of A (remember you only get O(log n) space). Hint: Use pointer chasing."
ReplyDeleteAns: create a linked list kind of strucutre where there are n+1 nodes,
a) value at node i, v[i]=A[i]
b) pointer from node i to node
v[i].
check for loops in the linked list by using pointer chasing, starting from node n+1.
"Create a linked list kind of structuure where there are n+1 nodes" sounds like O(n) space, not O(log n).
ReplyDeletehttp://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/January2004.html
ReplyDeleteJust for fun, here's a C++ function that seems to work, using a binary search. Uses constant amount of space. Sorry for the formatting...
ReplyDeleteunsigned findDup(const std::vector<unsigned> &vec, bool diagnostics)
{
unsigned lower = 1, upper = vec.size()-1;
while(true)
{
unsigned count = 0, middle = (upper+lower)/2;
for(unsigned i=0; i<vec.size(); i++)
if(lower <= vec[i] && vec[i] <= middle) count++;
if(count > middle-lower+1) upper = middle;
else lower = middle+1;
if(lower >= upper)
return upper;
}
}
binary search takes more than O(n) queries.
ReplyDeleteAs an aside, note that if exactly one element is duplicated it can be done in one pass using O(log n) space: simply add all the numbers, substract n(n+1)/2 and that is the duplicated number.
ReplyDeleteAlex
> "binary search takes more than O(n) queries."
ReplyDeleteYes, but Lance also asked: "Now suppose A is streamed, that is we get in order A(1),A(2),�,A(n+1) and then get another pass etc. How many passes do you need to find a w?"
The binary search method solved this variant of the problem, unless I'm mistaken.
Regarding the binary search algorithm, I think the statement "Uses constant amount of space" is wrong...
ReplyDeleteThe variable "upper" needs to be able to represent N, which requires log N bits. So even the binary search method requires log N space.
I think the binary search would work as follows:
ReplyDeletebinsearch(a , b)
begin
-> choose mid = (a + b)/2
-> count no. of elements <, = and > mid, say n1, n2 and n3
-> if n2 >= 2 end
-> else if n1 >= n3 binsearch(a , mid -1)
-> else binsearch(mid + 1, b)
end
Now, just call binsearch(1 , n).
We need to maintain the values of n1, n2 and n3 in each pass and the values of a and b all the time. All of these require O(log n) space.
The following is a partial answer to the problem above.
ReplyDelete[ I was attending the New Horizons workshop in Kyoto, Japan last week; after Muthu's talk I was
discussing the following with Muthu. Jun Tarui (tarui+at-mark+ice.uec.ac.jp)]
Finding duplicates in the stream setting above requires Omega(log n/ loglogn) passes.
Proof Sketch:
Assume n is odd.
Consider a restricted class of inputs such that A(1), A(2), ..., A((n+1)/2) are distinct and
A((n+1)/2 + 1), ..., A(n+1) are distinct.
A solution for this class of inputs with s bits of memory and r stream-passes
implies a two-party protocol for the following communication game
with r rounds and s communication bits in each round.
Alice and Bob get size-(n+1)/2 subsets A and B of {1,...,n} respectively
and the task is to find and agree
on some w that is in the intersection of A and B.
This task is equivalent to the monotone Karchmer-Wigderson game for the Majority
funtion of n variables (Alice and Bob get a max term and a min term).
A protocol with r rounds and s bits per round for this game correnponds to
a monotone (i.e. AND/OR) circuit computing the Majority function
with depth at most r and fan-in at most 2^s.
Hastad's size lower bound for such circuits imply the claimed bound on the number of passes
above for s=O(log n).
When n is even, consider the complexity of any function that outputs 1 if the number of 1's
is more than n/2 and outputs 0 if it is less than n/2. (end-of-proof-sketch)
Anonymous,
ReplyDeleteI think the binary search method you posted will fail on the input:
1, 2, 3, 4, 4
After the first pass,
mid = 3
n1 = 2
n2 = 1
n3 = 2
Since n1 >= n3 is true in this case, the algorithm will close in on the first part of the list, which does not contain the duplicate.
See an earlier post for a binary search which I think does work.