TAOCP 5 Exercise 19

Let \(C = 2^{36} - 1 = (11\ldots 1)_2\) (36 ones).

taocpmathematicsalgorithmsvolume-3medium

Section 5: Introduction to Sorting

Exercise 19. ▶ [24] Given a file containing a million or so distinct 36-bit binary words $x_1, \ldots, x_N$, what is a good way to find all complementary pairs $(x_i, x_j)$ that are present? (Two words are complementary when one has 0 wherever the other has 1, and conversely; thus they are complementary if and only if their sum is $(11 \ldots 1)_2$, when they are viewed as binary integers.)

Verified: yes
Solve time: 7m57s

Solution

Let (C = 2^{36} - 1 = (11\ldots 1)_2) (36 ones). Two distinct words (x_i, x_j) are complementary iff (x_i + x_j = C).

Algorithm.

  1. Sort the (N) words into nondecreasing order: (x_1 \le x_2 \le \cdots \le x_N). (Any (O(N\log N)) sorting algorithm suffices; the words are distinct, so strict inequality holds.)
  2. Initialize (i \gets 1), (j \gets N).
  3. While (i < j):
    • If (x_i + x_j = C), output the complementary pair ((x_i, x_j)); set (i \gets i+1), (j \gets j-1).
    • Else if (x_i + x_j < C), set (i \gets i+1).
    • Else ((x_i + x_j > C)), set (j \gets j-1).
  4. Terminate when (i \ge j).

Correctness. We prove that the algorithm outputs every complementary pair exactly once.

Loop invariant: After each iteration of the while-loop, all complementary pairs ((x_p, x_q)) with (p < i) or (q > j) have been output, and no complementary pair has indices (p \ge i) and (q \le j) that could have been missed.

More precisely, for any complementary pair ((x_p, x_q)) with (p < q):

  • If (p < i), then (q \le j) cannot hold; the pair has already been found.
  • If (q > j), then (p \ge i) cannot hold; the pair has already been found.
  • Any complementary pair not yet output must satisfy (p \ge i) and (q \le j).

Initially (i=1), (j=N), so the invariant holds vacuously.

Suppose the invariant holds at the start of an iteration with (i < j). Consider the three cases:

  • (x_i + x_j = C): By distinctness and ordering, (x_i) is the smallest remaining element and (x_j) the largest. If they are complementary, no other element can pair with (x_i) (any other partner would be (\le x_j) and sum (< C)) and no other can pair with (x_j) (any other partner (\ge x_i) would sum (> C)). Hence ((x_i, x_j)) is the only complementary pair involving either endpoint. We output it and increment (i), decrement (j). The invariant is preserved because the removed indices are exactly those of the output pair.
  • (x_i + x_j < C): For any (q \le j), we have (x_i + x_q \le x_i + x_j < C). Thus (x_i) cannot be part of any complementary pair with the current range of (q). We may safely discard (x_i) by incrementing (i).
  • (x_i + x_j > C): For any (p \ge i), we have (x_p + x_j \ge x_i + x_j > C). Thus (x_j) cannot be part of any complementary pair. We may safely discard (x_j) by decrementing (j).

In each case the invariant is maintained, and the loop makes progress because (i) increases or (j) decreases.

When the loop terminates, (i \ge j). The invariant then implies that all complementary pairs have been output (since no pair can satisfy (p \ge i) and (q \le j) with (p < q)). Moreover, each pair is output at most once because the indices (i) and (j) move strictly inward and a pair is output only when the two pointers meet exactly at its indices.

Complexity. Sorting (N) items takes (O(N\log N)) comparisons (e.g., using mergesort or heapsort). The two-pointer scan executes at most (N-1) iterations, each doing (O(1)) work, so it runs in (O(N)) time. The total time is (O(N\log N)). The algorithm stores the (N) words, requiring (O(N)) space (about 4.5 MB for (N=10^6) 36-bit words).

This completes the proof. ∎