A positive integer N is given. Consider the sequence of numbers [0, 1, ..., N]. What is the total number of zeros in the decimal representations of these numbers?
N can be very large. Hence, it is given in the form of a non-empty string S of length L, containing a decimal representation of N. S contains no leading zeros.
Write a function:
class Solution { public int solution(String S); }
that, given a string S, which is a decimal representation of some positive integer N, returns the total number of zeros in the decimal representations of numbers [0, 1, ..., N]. If the result exceeds 1,410,000,016, the function should return the remainder from the division of the result by 1,410,000,017.
For example, for S="100" the function should return 12 and for S="219" it should return 42.
Write an efficient algorithm for the following assumptions:
- L is an integer within the range [1..10,000];
- string S consists only of digits (0−9);
- string S contains no leading zeros.