Python O(1):
Since the challenge has been specified to be using Big O. I concluded that the best way to do it(since the upper bound is limited by a constant) is to just to create a giant look-up array.
However, this program would be too big to post here, so I made a program that generates it:
def zeroesUpToN(n):
zeros = 0
for i in range(n):
s = str(i+1)
zeros += s.count('0')
return zeros
s = "print(["
for i in range(10^10000):
s += str(zeroesUpToN(i+1)) + ",";
s = s[:-1] + "][int(input())])"
print(s)
So, this will ALWAYS take a long time to run(I mean the resulting program, not the generating program. The generating program would take even longer). But, how long it takes to run will not depend on n. Therefore, by definition it is an O(1) solution.
Here is an actual program that works for smaller outputs(up to 200):
print([0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,11,12,13,14,15,16,17,18,19,20,21,21,21,21,21,21,21,21,21,21,22,22,22,22,22,22,22,22,22,22,23,23,23,23,23,23,23,23,23,23,24,24,24,24,24,24,24,24,24,24,25,25,25,25,25,25,25,25,25,25,26,26,26,26,26,26,26,26,26,26,27,27,27,27,27,27,27,27,27,27,28,28,28,28,28,28,28,28,28,28,29,29,29,29,29,29,29,29,29,29,31][int(input())])
The real one is obviously much bigger.
P.S This is the problem with Big O problems.
EDIT: Oops, I forgot to give credit to @user2509848 whom I actually stole the code for generating each N.
most efficient
isn't particularly well defined. Do you mean in Big O complexity? Benchmark? If we measure straight time, it's unfair if I have an 8 core processor and parallelise this. \$\endgroup\$