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.
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.