zeroest pair sum


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 
  
 $