Stream the numbers. Push v[i] into a hash table. Lookup into a hash table for the value x-v[i] to exist.. if it does, output v[i] and x-v[i].
Tougher problem: do this with a fixed amount of memory (ruling out a hash table for all the numbers) Though I suppose you could do it with a fixed size hash table and just use multiple passes to cover the range.
Stream the numbers. Push v[i] into a hash table. Lookup into a hash table for the value x-v[i] to exist.. if it does, output v[i] and x-v[i].
ReplyDeleteTougher problem: do this with a fixed amount of memory (ruling out a hash table for all the numbers) Though I suppose you could do it with a fixed size hash table and just use multiple passes to cover the range.