5 ms·
This problem (reportedly) took Don Knuth, 24 hours to solve
- informatimago 11y agoI don't know what was Knuth's solution, but it's trivial: (- (reduce '+ vector) (let ((n (- (length vector) 2))) (/ (* n (+ n 1)) 2))) reduce is O(n) time and O(1) space. length is O(1) time and space. Notice also that if there are no duplicates, this formula will give the maximum element (- (length vector) 1).