Quote:Original post by Zipster Again, could be more edge cases I'm missing.
This is quickly beginning to look like my original solution (check the OP). It solves in Log10(n) time and is pretty much the same math, just broken up a bit. I might be doing an unnecessary piece of algebra, as I have not combed over it for redundant operations to preserve the steps I took to arrive at it.
Edit: I was hoping to find a way to mathematically eliminate the logical statements (if statements) and reduce it to a formulaic form. Perhaps it isn't possible?
import mathdef digit(n, k): return n/(10**(k)) % 10def right(n, k): if k == 0: return 0 return n % 10**(k)def left(n, k): return n / 10**(k+1) def ones(n): ret = 0 for i in range(0, int(math.log10(n)+1)): pow10 = 10**i d = digit(n, i) r = right(n, i) l = left(n, i) ret = ret + l*(pow10) if d == 1: ret = ret + r + 1 if d >= 2: ret = ret + pow10 return ret
Ok, i am pretty sure this is right. In addition it does run in log10 time, so its still fast, but your right there are a few cases that ake this ugly. it may be possible to do better, but remember the number of 1's up to a number is not a natural mathematical concept, its a side effect of our way of concieving them, so don't wory about it being too pretty. thanks for the cool problem ... if this is wrong, let me know.
EDIT: Fixed mistake
[Edited by - ibebrett on March 31, 2010 9:59:17 PM]
check this database out we can validate against it.
and i fixed my solution above, i am 99% its right now (which i was before of course..)
Yes, your solution looks identical to my solution (2nd code block in the op). I think it is probably the best one. The reason I was thinking there might be a mathematical solution is because this problem is based on probability. However, it does seem that the probability is spatial (relates to digit position) and cannot be solved as a set. Ah well, it was indeed fun to solve.
