Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.
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.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.