[buug] substring of integers problem
Ian Zimmerman
itz at buug.org
Sat Feb 5 20:26:25 PST 2011
Karen> Oh. O.k. Hmm. And you don't think it's NP-Complete...if not
Karen> then dynamic programming will probably solve it, but I would have
Karen> to think awhile, maybe a long while, to figure out how.
My solution is O(n log n) where n is the size of the input - I didn't do
a formal proof, but it's clear from the structure of it and I did run
huge randomized tests with multiple input sizes which confirmed it.
--
Ian Zimmerman <itz at buug.org>
gpg public key: 1024D/C6FF61AD
fingerprint: 66DC D68F 5C1B 4D71 2EE5 BD03 8A00 786C C6FF 61AD
Ham is for reading, not for eating.
More information about the buug
mailing list