[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