News for hackers. Stuff that matters.
Re:The Great Theorem Prover Showdown by dbkaplun on Thursday April 26, 2018 @08:59AM (#16931438)
> Fulcrum. Given a sequence of integers, returns the index i that minimizes |sum(seq[..i]) - sum(seq[i..])|. Does this in O(n) time and O(n) memory.

This is doable in O(n) time and O(1) memory. Sum the list once. Then start from the beginning, collecting a running total and subtracting from the sum for a running difference.

There are no comments on this comment yet.