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:
zeros = 0
for i in range(n):
s = str(i+1)
zeros += s.count('0')
s = "print(["
for i in range(10^10000):
s += str(zeroesUpToN(i+1)) + ",";
s = s[:-1] + "][int(input())])"
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):
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.