Here's a summary of Dimitris Andreou's link.
Remember sum of i-th powers, where i=1,2,..,k. This reduces the problem to solving the system of equations
a1 + a2 + ... + ak = b1
a12 + a22 + ... + ak2 = b2
...
a1k + a2k + ... + akk = bk
Using Newton's identities, knowing bi allows to compute
c1 = a1 + a2 + ... ak
c2 = a1a2 + a1a3 + ... + ak-1ak
...
ck = a1a2 ... ak
If you expand the polynomial (x-a1)...(x-ak) the coefficients will be exactly c1, ..., ck - see Viète's formulas. Since every polynomial factors uniquely (ring of polynomials is an Euclidean domain), this means ai are uniquely determined, up to permutation.
This ends a proof that remembering powers is enough to recover the numbers. For constant k, this is a good approach.
However, when k is varying, the direct approach of computing c1,...,ck is prohibitely expensive, since e.g. ck is the product of all missing numbers, magnitude n!/(n-k)!. To overcome this, perform computations in Zq field, where q is a prime such that n <= q < 2n - it exists by Bertrand's postulate. The proof doesn't need to be changed, since the formulas still hold, and factorization of polynomials is still unique. You also need an algorithm for factorization over finite fields, for example the one by Berlekamp or Cantor-Zassenhaus.
High level pseudocode for constant k:
- Compute i-th powers of given numbers
- Subtract to get sums of i-th powers of unknown numbers. Call the sums bi.
- Use Newton's identities to compute coefficients from bi; call them ci. Basically, c1 = b1; c2 = (c1b1 - b2)/2; see Wikipedia for exact formulas
- Factor the polynomial xk-c1xk-1 + ... + ck.
- The roots of the polynomial are the needed numbers a1, ..., ak.
For varying k, find a prime n <= q < 2n using e.g. Miller-Rabin, and perform the steps with all numbers reduced modulo q.
EDIT: The previous version of this answer stated that instead of Zq, where q is prime, it is possible to use a finite field of characteristic 2 (q=2^(log n)). This is not the case, since Newton's formulas require division by numbers up to k.
Sorting solutions have been proposed, but sorting is a little too much: We don't need order; we just need equality groups.
So hashing would be enough (and faster).
- For each color of socks, form a pile. Iterate over all socks in your input basket and distribute them onto the color piles.
- Iterate over each pile and distribute it by some other metric (e.g. pattern) into the second set of piles
- Recursively apply this scheme until you have distributed all socks onto very small piles that you can visually process immediately
This kind of recursive hash partitioning is actually being done by SQL Server when it needs to hash join or hash aggregate over huge data sets. It distributes its build input stream into many partitions which are independent. This scheme scales to arbitrary amounts of data and multiple CPUs linearly.
You don't need recursive partitioning if you can find a distribution key (hash key) that provides enough buckets that each bucket is small enough to be processed very quickly. Unfortunately, I don't think socks have such a property.
If each sock had an integer called "PairID" one could easily distribute them into 10 buckets according to PairID % 10
(the last digit).
The best real-world partitioning I can think of is creating a rectangle of piles: one dimension is color, the other is the pattern. Why a rectangle? Because we need O(1) random-access to piles. (A 3D cuboid would also work, but that is not very practical.)
Update:
What about parallelism? Can multiple humans match the socks faster?
- The simplest parallelization strategy is to have multiple workers take from the input basket and put the socks onto the piles. This only scales up so much - imagine 100 people fighting over 10 piles. The synchronization costs (manifesting themselves as hand-collisions and human communication) destroy efficiency and speed-up (see the Universal Scalability Law!). Is this prone to deadlocks? No, because each worker only needs to access one pile at a time. With just one "lock" there cannot be a deadlock. Livelocks might be possible depending on how the humans coordinate access to piles. They might just use random backoff like network cards do that on a physical level to determine what card can exclusively access the network wire. If it works for NICs, it should work for humans as well.
- It scales nearly indefinitely if each worker has its own set of piles. Workers can then take big chunks of socks from the input basket (very little contention as they are doing it rarely) and they do not need to synchronise when distributing the socks at all (because they have thread-local piles). At the end, all workers need to union their pile-sets. I believe that can be done in O(log (worker count * piles per worker)) if the workers form an aggregation tree.
What about the element distinctness problem? As the article states, the element distinctness problem can be solved in O(N)
. This is the same for the socks problem (also O(N)
, if you need only one distribution step (I proposed multiple steps only because humans are bad at calculations - one step is enough if you distribute on md5(color, length, pattern, ...)
, i.e. a perfect hash of all attributes)).
Clearly, one cannot go faster than O(N)
, so we have reached the optimal lower bound.
Although the outputs are not exactly the same (in one case, just a boolean. In the other case, the pairs of socks), the asymptotic complexities are the same.
Best Answer
Use in-place radix sort and OP's first solution with 2 iterators, coming towards each other.
If numbers in the array are not some sort of multi-precision numbers and are, for example, 32-bit integers, you can sort them in 2*32 passes using practically no additional space (1 bit per pass). Or 2*8 passes and 16 integer counters (4 bits per pass).
Details for the 2 iterators solution:
First iterator initially points to first element of the sorted array and advances forward. Second iterator initially points to last element of the array and advances backward.
If sum of elements, referenced by iterators, is less than the required value, advance first iterator. If it is greater than the required value, advance second iterator. If it is equal to the required value, success.
Only one pass is needed, so time complexity is O(n). Space complexity is O(1). If radix sort is used, complexities of the whole algorithm are the same.
If you are interested in related problems (with sum of more than 2 numbers), see "Sum-subset with a fixed subset size" and "Finding three elements in an array whose sum is closest to an given number".