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.