All pairs of numbers A.I, A.J with A.I+A.J=X

PROBLEM
Given an array of distinct numbers A.1,A.2,...,A.N and a number X. Determine all pairs of numbers A.I,A.J with A.I+A.J=X.

IMPLEMENTATION
Unit: fragment of a program
 
Interface: QUICKSORT
 
Result: Program displays all pairs A.I,A.J with A.I+A.J=X
 

...
call QUICKSORT N
S = ""; do I = 1 to N; S = S A.I; end; say S "|" X
I = 1; J = N
do until J <= I
  select
  when A.I + A.J < X then I = I + 1
  when A.I + A.J > X then J = J - 1
  otherwise
    say "("A.I"," A.J") and ("A.J"," A.I")"
    I = I + 1; J = J - 1
  end
end
if J = I & 2 * A.I = X then say "("A.I"," A.I")"
exit
...

 

Literature
Knuth D. E. Sorting and Searching, vol. 3 of The Art of Computer Programming
Addison-Wesley, 1973


Cover Contents Index Main page

last modified 30th July 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic