Given an integer set, find the integer pair with a sum is closest to zero.
Unlike the boring O(n^2) solution, generating non-trivial (that is, positive and negative valued) test data seems to be as hard as coming up with a linear solution to the problem.
$ cat mi.scm #lang racket (require rackunit) (define (avp a b) (abs (+ a b))) (define (minimum-interval i-vec) (let* ((n (vector-length i-vec)) (min-a (vector-ref i-vec 0)) (min-b (vector-ref i-vec 1)) (min-s (avp min-a min-b))) (do ((i (- n 1) (- i 1))) ((< i 1) (values min-a min-b)) (let ((a (vector-ref i-vec i))) (do ((j (- i 1) (- j 1))) ((< j 0)) (let* ((b (vector-ref i-vec j)) (s (avp a b))) (when (> min-s s) (set! min-a a) (set! min-b b) (set! min-s s)))))))) (define (test-run) (define (rn) (+ (random 100) 1)) (define (make-vec mn mx) (let loop ((i (rn)) (l (list mx mn))) (if (< i 0) (list->vector (shuffle l)) (loop (- i 1) (cons (+ (rn) (car l)) l))))) (let* ((a (rn)) (b (rn)) (v (make-vec (min a b) (max a b)))) (let-values (((nmx pmn) (minimum-interval v))) (check-eq? (avp nmx pmn) (avp a b))))) (let loop ((i 0)) (test-run) (if (> i 100) #t (loop (+ i 1)))) $ mzscheme mi.scm #t $