Подсчитайте количество вхождений 0 в целые числа от 1 до N

Ответ 1

Обновленный ответ

Мой оригинальный ответ был прост для понимания, но сложным для кода. Здесь кое-что, что проще кодировать. Это прямое нерекурсивное решение, которое работает, подсчитывая количество способов, когда нули могут появляться в каждой позиции.

Например:

x <= 1234. Сколько чисел существует из следующей формы?

x = 0 0?

Существует 12 возможностей для "сотен или более" (1,2,..., 12). Тогда должен быть ноль. Тогда есть 10 возможностей для последней цифры. Это дает 12 * 10 = 120 числа, содержащие 0 на третьей цифре.

Таким образом, решение для диапазона (от 1 до 1234):

• ? 0??: 1 * 100 = 100
• ?? 0?: 12 * 10 = 120
• 0: 123
• Всего = 343

Но исключение - если n содержит нулевую цифру. Рассмотрим следующий случай:

x <= 12034. Сколько чисел существует в следующей форме?

x = 0 0

У нас есть 12 способов выбрать "тысячи или больше". Для 1, 2,... 11 мы можем выбрать любые две последние цифры (дающие 11 * 100 возможностей). Но если мы начнем с 12, мы можем выбрать только число между 00 и 34 для двух последних цифр. Таким образом, мы получаем возможности 11 * 100 + 35 вообще.

Здесь реализована реализация этого алгоритма (написанная на Python, но так, чтобы ее было легко переносить на C):

def countZeros(n):
    result = 0
    i = 1

    while True:
        b, c = divmod(n, i)
        a, b = divmod(b, 10)

        if a == 0:
            return result

        if b == 0:
            result += (a - 1) * i + c + 1
        else:
            result += a * i

        i *= 10

Ответ 2

Я бы предложил адаптировать этот алгоритм от основания 2 к основанию 10:

Число 1 в двоичных представлениях двоичных представлений целых чисел в диапазоне

Результирующим алгоритмом является O (log N).

Подход состоит в том, чтобы написать простую рекурсивную функцию count(n), которая считает нули от 1 до n.

Главное наблюдение заключается в том, что если N заканчивается на 9, например:

123456789

Вы можете поместить числа от 0 до N в 10 групп равного размера. Группа 0 - это числа, заканчивающиеся на 0. Группа 1 - это числа, оканчивающиеся на 1. Группа 2 - это числа, оканчивающиеся на 2. И так далее, все через группу 9, которые являются всеми числами, заканчивающимися на 9.

Каждая группа, кроме группы 0, вносит count(N/10) нулевые цифры в итоговое значение, потому что ни одна из них не заканчивается на ноль. Группа 0 вносит вклад count(N/10) (который подсчитывает все цифры, но последние) плюс N/10 (который отсчитывает нули от окончательных цифр).

Так как мы переходим от 1 до N вместо 0 в N, эта логика ломается для одноразрядного N, поэтому мы просто обрабатываем это как частный случай.

[обновление]

Какая черта, пусть обобщает и определяет count(n, d), сколько раз число d появляется среди чисел от 1 до n.

/* Count how many d occur in a single n */
unsigned
popcount(unsigned n, unsigned d) {
  int result = 0;
  while (n != 0) {
    result += ((n%10) == d);
    n /= 10;
  }
  return result;
}

/* Compute how many d occur all numbers from 1 to n */
unsigned
count(unsigned n, unsigned d) {
  /* Special case single-digit n */
  if (n < 10) return (d > 0 && n >= d);

  /* If n does not end in 9, recurse until it does */
  if ((n % 10) != 9) return popcount(n, d) + count(n-1, d);

  return 10*count(n/10, d) + (n/10) + (d > 0);
}

Уродство для случая n < 10 снова происходит от диапазона от 1 до n вместо 0 до n... Для любой одноразрядной n больше или равной d, count равен 1, за исключением случаев, когда d равно нулю.

Преобразование этого решения в цикл нерекурсивный: (a) тривиально, (b) ненужно и (c) оставлено как упражнение для читателя.

[Обновить 2]

Конечный член (d > 0) также исходит из диапазона от 1 до n вместо 0 до n. Когда n заканчивается на 9, количество чисел между 1 и n включительно имеет окончательную цифру d? Ну, когда d равно нулю, ответ N/10; когда d отличен от нуля, это еще одно, поскольку оно включает в себя значение d.

Например, если n равно 19, а d равно 0, остается только одно меньшее число, заканчивающееся на 0 (т.е. 10). Но если n равно 19, а d равно 2, то есть два меньших числа, заканчивающиеся на 2 (т.е. 2 ​​и 12).

Благодаря @Chan для указания этой ошибки в комментариях; Я исправил его в коде.

Ответ 3

Пусть Z(n) = #zero digits in numbers 0 <= k < n. Очевидно, Z(0) = 0.

Если n = 10*k + r, 0 <= r <= 9, все 10*k числа 10*j + s, 0 <= j < k, 0 <= s <= 9 находятся в диапазоне, каждая десятая последняя цифра равна 0, так что k нули и каждый префикс j (все, кроме последней цифры) появляются десять раз, но мы не должны считать 0, поэтому число нулей в префиксах 10*(Z(k)-1).

Число нулей в r числах 10*k, ..., 10*k + (r-1) равно r*number of zeros in k + (r > 0 ? 1 : 0).

Итак, у нас есть алгоритм O(log n) для вычисления Z(n)

unsigned long long Z(unsigned long long n)
{
    if (n == 0) {
        return 0;
    }
    if (n <= 10) {
        return 1;
    }
    unsigned long long k = n/10, r = n%10;
    unsigned long long zeros = k + 10*(Z(k)-1);
    if (r > 0) {
        zeros += r*zeroCount(k) + 1;
    }
    return zeros;
}

unsigned zeroCount(unsigned long long k)
{
    unsigned zeros = 0;
    while(k) {
        zeros += (k % 10) == 0;
        k /= 10;
    }
    return zeros;
}

Чтобы вычислить число для произвольного диапазона,

unsigned long long zeros_in_range(unsigned long long low, unsigned long long high)
{
    return Z(high+1) - Z(low); // beware of overflow if high is ULLONG_MAX
}

Ответ 4

Как я подошел к этой проблеме:

числа могут находиться в диапазоне от 1 до N:

Итак, я разбил это на диапазоны следующим образом:

Rangle      : #Digits   :   #Zeros
1   -   9   :   1       :   0
10  -   99  :   2       :   9 (number of all the possible digits when zero is at units place=> _0 ie, 1,2,3,4,5,6,7,8,9
100 -   199 :   3       :   20 => 10 (#digits when zero is at units place) + 10 (#digits when zero is at tens place)
200 -   276 :   3       :   18 => 8 (#digits when zero is at units place) + 10 (#digits when zero is at tens place)
300 -   308 :   3       :   10 => 1 (#digits when zero is at units place) + 9 (#digits when zero is at tens place)
1000-   1008:   4       :   19 => 1 + 9 + 9

Теперь для любого заданного диапазона 1 - N я хочу иметь возможность разбить число на эти диапазоны и использовать приведенную выше логику для вычисления числа нулей.

Тестирование:

для заданного числа N:

- compute number of digits: len
- if len = 1 : d1: return 0
- len = 2: d2_temp: count # of digits that can possibly occur when 0 is at unit place 
            : for e.g. 76: so numbers can be between 10 - 76: (7 - 1) + 1 = 7
         : d2: sum(d2_temp, d1)
- len = 3: return d3 : sum(d3_temp, d2)
         : compute d3_temp: 
         : for e.g. n = 308 : get digit at 10^(len-1) : loopMax 3
         : d3_temp1: count number of zeros for this loop: 1 * 100 to (loopMax -1) * 100 : (loopMax-1) * 20
         : d3_temp2: for n count (#digits when zero is at units place) + (#digits when zero is at tens place)
         : d3_temp = d3_temp1 + d3_temp2

Давайте попробуем обобщить:

99 : sum( , )
    : d3_temp: 
    : loopMax: n = 99 : n/(10^1) : 9
    : d3_temp1: 8 : (9-1) * (10*(len-1)) : (loopMax - 1) * 10 * (len-1)
    : d3_temp2: 1 : for len, count #0s in range (loopMax * 10 * (len-1)) to n : count(90, 99)
    : d3_temp = 8 + 1
    : sum(9, 0)
    : 9

У меня возникли проблемы с этим, но это сработает.

Ответ 5

class FindZero{

    public int findZero(int lastNumber){

        int count=1,k;
        if(lastNumber<10)
            return 0;
        else if(lastNumber==10)
            return 1;
        else{

            for(int i=11;i<=lastNumber;i++){
                k=i;
                while(k>0){

                    if(k%10==0)
                        count++;
                        k=k/10;
                }
            }
            return count;
        }
    }
    public static void main(String args[]){
        FindZero obj = new FindZero();
        System.out.println(obj.findZero(1234));
    }
}