Рубрики

Подсчитать числа, имеющие цифру 0

Проблема: Подсчитайте, сколько целых чисел от 1 до N содержит 0 в виде цифры.

Примеры:

Input:  n = 9
Output: 0

Input: n = 107
Output: 17
The numbers having 0 are 10, 20,..90, 100, 101..107

Input: n = 155
Output: 24
The numbers having 0 are 10, 20,..90, 100, 101..110,
120, ..150.

Наивное решение обсуждается в предыдущем посте

В этом посте обсуждается оптимизированное решение. Давайте внимательно проанализируем проблему.

Пусть данное число имеет d цифр.

Требуемый ответ может быть вычислен путем вычисления следующих двух значений:

  1. Количество целых чисел 0, имеющих максимум d-1 цифр.
  2. Количество целых чисел 0, имеющих ровно d цифр (меньше или равно заданному числу, конечно!)

Таким образом, решение будет сумма двух выше.

Первая часть уже обсуждалась здесь .

Как найти вторую часть?
Мы можем найти общее количество целых чисел, имеющих d цифр (меньше, чем заданное число), которые не содержат нулей.

Чтобы найти это, мы пересекаем число, по одной цифре за раз.

Мы находим количество неотрицательных целых чисел следующим образом:

  1. Если число в этом месте равно нулю, уменьшите счетчик на 1 и разбейте (потому что мы не можем двигаться дальше, уменьшите, чтобы убедиться, что само число содержит ноль)
  2. иначе умножьте (число-1) на степень (9, число цифр справа от него)

Давайте проиллюстрируем на примере.

Let the number be n = 123. non_zero = 0
We encounter 1 first, 
 add (1-1)*92  to non_zero (= 0+0)

We encounter 2, 
 add (2-1)*91 to non_zero (= 0+9 = 9)

We encounter 3, 
 add (3-1)*90 to non_zero (=9+3 = 12)

Мы можем заметить, что non_zero обозначает число целое число, состоящее из 3 цифр (не более 123) и не содержит нуля. (111, 112,… .., 119, 121, 122, 123) (рекомендуется проверить один раз)

Теперь можно спросить, какой смысл рассчитывать количество чисел, у которых нет нулей?

Верный! нам интересно найти количество целых чисел, которые имеют ноль.

Однако теперь мы можем легко найти это, вычитая non_zero из n после игнорирования наиболее значимого места. То есть, в нашем предыдущем примере zero = 23 — non_zero = 23-12 = 11 и, наконец, мы добавляем две части, чтобы получить требуемый результат !!

Ниже приведена реализация вышеуказанной идеи.

C ++

// Модифицированная программа C ++ для подсчета числа от 1 до n с
// 0 как цифра.
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает количество целых чисел от нуля до заданных цифр

int zeroUpto(int digits)

{

    // Подробности смотрите ниже в статье

    // https://www.geeksforgeeks.org/count-positive-integers-0-digit/amp/

    int first = (pow(10,digits)-1)/9;

    int second = (pow(9,digits)-1)/8;

    return 9 * (first - second);

}

  
// служебная функция для преобразования представления символов
// в целое число

int toInt(char c)

{

    return int(c)-48;

}

  
// считает числа, имеющие ноль, цифрами до заданного
// число 'num'

int countZero(string num)

{

    // k обозначает количество цифр в номере

    int k = num.length();

  

    // Вычисление общего числа, имеющего нули,

    // которые до k-1 цифр

    int total = zeroUpto(k-1);

  

    // Теперь давайте посчитаем числа, которых нет

    // любые нули. В этом k цифр до заданного числа

    int non_zero = 0;

    for (int i=0; i<num.length(); i++)

    {

        // Если само число содержит ноль, то

        // уменьшить счетчик

        if (num[i] == '0')

        {

            non_zero--;

            break;

        }

  

        // Добавляем количество ненулевых чисел, которые

        // можно сформировать

        non_zero += (toInt(num[i])-1) * (pow(9,k-1-i));

    }

  

    int no = 0, remaining = 0,calculatedUpto=0;

  

    // Подсчитаем число и оставшиеся после

    // игнорируем самую значимую цифру

    for (int i=0; i<num.length(); i++)

    {

        no = no*10 + (toInt(num[i]));

        if (i != 0)

            calculatedUpto = calculatedUpto*10 + 9;

    }

    remaining = no-calculatedUpto;

  

    // Окончательный ответ рассчитывается

    // Он рассчитывается путем вычитания 9 .... 9 (d-1) раз

    // из №

    int ans = zeroUpto(k-1) + (remaining-non_zero-1);

    return ans;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    string num = "107";

    cout << "Count of numbers from 1" << " to "

         << num << " is " << countZero(num) << endl;

  

    num = "1264";

    cout << "Count of numbers from 1" << " to "

         << num << " is " <<countZero(num) << endl;

  

    return 0;

}

Джава

// Модифицированная Java-программа для подсчета числа от 1 до n с
// 0 как цифра.

  

public class GFG {

  

  
// Возвращает количество целых чисел от нуля до заданных цифр

static int zeroUpto(int digits)

{

    // Подробности смотрите ниже в статье

    // https://www.geeksforgeeks.org/count-positive-integers-0-digit/amp/

    int first = (int) ((Math.pow(10,digits)-1)/9);

    int second = (int) ((Math.pow(9,digits)-1)/8);

    return 9 * (first - second);

}

   
// служебная функция для преобразования представления символов
// в целое число

static int toInt(char c)

{

    return (int)(c)-48;

}

   
// считает числа, имеющие ноль, цифрами до заданного
// число 'num'

static int countZero(String num)

{

    // k обозначает количество цифр в номере

    int k = num.length();

   

    // Вычисление общего числа, имеющего нули,

    // которые до k-1 цифр

    int total = zeroUpto(k-1);

   

    // Теперь давайте посчитаем числа, которых нет

    // любые нули. В этом k цифр до заданного числа

    int non_zero = 0;

    for (int i=0; i<num.length(); i++)

    {

        // Если само число содержит ноль, то

        // уменьшить счетчик

        if (num.charAt(i) == '0')

        {

            non_zero--;

            break;

        }

   

        // Добавляем количество ненулевых чисел, которые

        // можно сформировать

        non_zero += (toInt(num.charAt(i))-1) * (Math.pow(9,k-1-i));

    }

   

    int no = 0, remaining = 0,calculatedUpto=0;

   

    // Подсчитаем число и оставшиеся после

    // игнорируем самую значимую цифру

    for (int i=0; i<num.length(); i++)

    {

        no = no*10 + (toInt(num.charAt(i)));

        if (i != 0)

            calculatedUpto = calculatedUpto*10 + 9;

    }

    remaining = no-calculatedUpto;

   

    // Окончательный ответ рассчитывается

    // Он рассчитывается путем вычитания 9 .... 9 (d-1) раз

    // из №

    int ans = zeroUpto(k-1) + (remaining-non_zero-1);

    return ans;

}

   
// Программа драйвера для проверки вышеуказанных функций

  

    static public void main(String[] args) {

        String num = "107";

    System.out.println("Count of numbers from 1" + " to "

         + num + " is " + countZero(num));

   

    num = "1264";

    System.out.println("Count of numbers from 1" + " to "

         + num + " is " +countZero(num));

    }

}

  
// Этот код предоставлен 29AjayKumar

python3

# Python3 программа для подсчета числа от 1 до n
# с 0 в качестве цифры.

  
# Возвращает количество целых чисел, имеющих ноль
# до заданных цифр

def zeroUpto(digits):

      

    first = int((pow(10, digits) - 1) / 9); 

    second = int((pow(9, digits) - 1) / 8); 

    return 9 * (first - second); 

  
# считает числа, имеющие ноль в виде цифр
# до заданного числа 'num'

def countZero(num): 

      

    # k обозначает количество цифр

    № в номере

    k = len(num); 

  

    # Расчет общего количества, имеющего

    # нули, которые до k-1 цифр

    total = zeroUpto(k - 1); 

  

    # Теперь давайте посчитаем числа, которые

    # нет нулей. В этом к цифрах

    # до заданного числа

    non_zero = 0

    for i in range(len(num)): 

          

        # Если само число содержит ноль

        # затем уменьшить счетчик

        if (num[i] == '0'):

            non_zero -= 1;

            break

  

        # Добавление количества ненулевых чисел

        # которые могут быть сформированы

        non_zero += (((ord(num[i]) - ord('0')) - 1) * 

                                (pow(9, k - 1 - i))); 

  

    no = 0

    remaining = 0

    calculatedUpto = 0

  

    # Рассчитать число и оставшиеся

    # после игнорирования самой значимой цифры

    for i in range(len(num)): 

        no = no * 10 + (ord(num[i]) - ord('0')); 

        if (i != 0): 

            calculatedUpto = calculatedUpto * 10 + 9

      

    remaining = no - calculatedUpto; 

  

    # Окончательный ответ рассчитывается. Рассчитано

    # вычитая 9 .... 9 (d-1) раз из нет.

    ans = zeroUpto(k - 1) + (remaining - non_zero - 1); 

    return ans; 

  
Код водителя

num = "107"

print("Count of numbers from 1 to"

        num, "is", countZero(num)); 

  

num = "1264"

print("Count of numbers from 1 to"

       num, "is", countZero(num)); 

  
# Этот код предоставлен mits

C #

// Модифицированная программа C # для подсчета числа от 1 до n с
// 0 как цифра.

  

using System;

public class GFG{

  
// Возвращает количество целых чисел от нуля до заданных цифр

static int zeroUpto(int digits) 

    // Подробности смотрите ниже в статье

    // https://www.geeksforgeeks.org/count-positive-integers-0-digit/amp/

    int first = (int) ((Math.Pow(10,digits)-1)/9); 

    int second = (int) ((Math.Pow(9,digits)-1)/8); 

    return 9 * (first - second); 

  
// служебная функция для преобразования представления символов
// в целое число

static int toInt(char c) 

    return (int)(c)-48; 

  
// считает числа, имеющие ноль, цифрами до заданного
// число 'num'

static int countZero(String num) 

    // k обозначает количество цифр в номере

    int k = num.Length; 

  

    // Вычисление общего числа, имеющего нули,

    // которые до k-1 цифр

    int total = zeroUpto(k-1); 

  

    // Теперь давайте посчитаем числа, которых нет

    // любые нули. В этом k цифр до заданного числа

    int non_zero = 0; 

    for (int i=0; i<num.Length; i++) 

    

        // Если само число содержит ноль, то

        // уменьшить счетчик

        if (num[i] == '0'

        

            non_zero--; 

            break

        

  

        // Добавляем количество ненулевых чисел, которые

        // можно сформировать

        non_zero += (toInt(num[i])-1) * (int)(Math.Pow(9,k-1-i)); 

    

  

    int no = 0, remaining = 0,calculatedUpto=0; 

  

    // Подсчитаем число и оставшиеся после

    // игнорируем самую значимую цифру

    for (int i=0; i<num.Length; i++) 

    

        no = no*10 + (toInt(num[i])); 

        if (i != 0) 

            calculatedUpto = calculatedUpto*10 + 9; 

    

    remaining = no-calculatedUpto; 

  

    // Окончательный ответ рассчитывается

    // Он рассчитывается путем вычитания 9 .... 9 (d-1) раз

    // из №

    int ans = zeroUpto(k-1) + (remaining-non_zero-1); 

    return ans; 

  
// Программа драйвера для проверки вышеуказанных функций

  

    static public void Main() { 

        String num = "107"

    Console.WriteLine("Count of numbers from 1" + " to "

        + num + " is " + countZero(num)); 

  

    num = "1264"

    Console.WriteLine("Count of numbers from 1" + " to "

        + num + " is " +countZero(num)); 

    

  
// Этот код предоставлен 29AjayKumar

PHP

<?php
// PHP-программа для подсчета
// число от 1 до n
// с 0 в качестве цифры.

  
// Возвращает количество целых
// с нуля до заданных цифр

function zeroUpto($digits)

{

      

    $first = (int)((pow(10, 

                    $digits) - 1) / 9);

    $second = (int)((pow(9, 

                    $digits) - 1) / 8);

    return 9 * ($first - $second);

}

  

  
// считает числа, имеющие
// ноль, как цифры до
// заданное число 'num'

function countZero($num)

{

    // k обозначает число

    // цифр в номере

    $k = strlen($num);

  

    // Подсчет суммы

    // число, имеющее нули,

    // которые до k-1 цифр

    $total = zeroUpto($k-1);

  

    // Теперь давайте посчитаем

    // числа, которые не

    // есть нули. В этом

    // k цифр до заданного

    // число

    $non_zero = 0;

    for ($i = 0; 

         $i < strlen($num); $i++)

    {

        // Если само число

        // содержит ноль

        // уменьшить счетчик

        if ($num[$i] == '0')

        {

            $non_zero--;

            break;

        }

  

        // Добавляем количество

        // ненулевые числа, которые

        // можно сформировать

        $non_zero += (($num[$i] - '0') - 1) * 

                      (pow(9, $k - 1 - $i));

    }

  

    $no = 0;

    $remaining = 0;

    $calculatedUpto = 0;

  

    // Рассчитать число

    // и оставшиеся после

    // игнорируем большинство

    // значащая цифра

    for ($i = 0; 

         $i < strlen($num); $i++)

    {

        $no = $no * 10 + ($num[$i] - '0');

        if ($i != 0)

            $calculatedUpto = $calculatedUpto

                                        10 + 9;

    }

      

    $remaining = $no - $calculatedUpto;

  

    // Окончательный ответ рассчитывается

    // рассчитывается вычитанием

    // 9 .... 9 (d-1) раз от №.

    $ans = zeroUpto($k - 1) + 

                   ($remaining

                    $non_zero - 1);

    return $ans;

}

  
// Код драйвера

$num = "107";

echo "Count of numbers from 1 to "

                     $num . " is "

             countZero($num) . "\n";

  

$num = "1264";

echo "Count of numbers from 1 to "

                     $num . " is "

                    countZero($num);

  
// Этот код добавлен
// по миц
?>


Выход:

Count of numbers from 1 to 107 is 17 
Count of numbers from 1 to 1264 is 315

Анализ сложности:

Сложность времени: O (d), где d — нет. из цифр т.е. O (log (n)
Вспомогательное пространство: O (1)

Эта статья предоставлена Ашутошем Кумаром . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Подсчитать числа, имеющие цифру 0

0.00 (0%) 0 votes