I don't know what was Knuth's solution, but it's trivial:<p><pre><code> (- (reduce '+ vector)
(let ((n (- (length vector) 2)))
(/ (* n (+ n 1)) 2)))
</code></pre>
reduce is O(n) time and O(1) space.
length is O(1) time and space.<p>Notice also that if there are no duplicates, this formula will give the maximum element (- (length vector) 1).