Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

#### NumberOfZeros

Compute total number of zeros in decimal representation of 1, ...., N.

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 is made only of digits (09);
• string S contains no leading zeros.