Рубрики

Считать положительные целые числа с 0 в качестве цифры и максимальные цифры 'd'

Дано число d, представляющее количество цифр числа. Найти общее количество натуральных чисел, которые содержат по крайней мере один ноль и состоят из d или менее цифр.

Examples:
Input : d = 1
Output : 0
There's no natural number of 1 digit that contains a zero.

Input : d = 2
Output : 9

Input : d = 3
Output : 180
For d = 3, we've to count numbers from 1 to 999, that have 
atleast one zero in them.
Similarly for d=4, we'd check every number from 1 to 9999. 

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

В основном это расширение ниже поста.

Посчитайте 'd' цифрой натуральных чисел с 0 в качестве цифры.

Если мы внимательно наблюдаем, проблема очень похожа на ту, которую мы обсуждали в нашем первом наборе. Для данного d мы можем получить требуемый ответ, если найдем числа, которые имеют 0 и состоят из цифр 1, 2, 3… .., d. Наконец, мы можем добавить их, чтобы получить вывод.

Ниже программа для того же.

C ++

// C ++ программа для поиска числа положительных целых чисел
// заданное количество цифр, содержащих как минимум один ноль
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает количество целых чисел 'd', имеющих 0 в качестве цифры

int findCount(int d)

{

    return 9*(pow(10,d-1) - pow(9,d-1));

}

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

int findCountUpto(int d)

{

    // Количество чисел с цифрами меньше чем

    // или равно d.

    int totalCount = 0;

    for (int i=1; i<=d; i++)

        totalCount += findCount(i);

  

    return totalCount;

}

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

int main()

{

    int d = 1;

    cout << findCountUpto(d) << endl;

  

    d = 2;

    cout << findCountUpto(d) << endl;

  

    d = 4;

    cout << findCountUpto(d) << endl;

    return 0;

}

Джава

// Java-программа для поиска количества
// положительное целое число от активного числа
// цифр, содержащих как минимум один ноль

import java.io.*;

import java.math.*;

  

class GFG {

      

    // Возвращает количество цифр 'd'

    // целые числа имеют цифру 0

    static int findCount(int d)

    {

        return 9 * (int)((Math.pow(10, d - 1

                         - Math.pow(9, d - 1)));

    }

      

    // полезная функция для подсчета

    // требуемый ответ

    static int findCountUpto(int d)

    {

        // Количество чисел с цифрами

        // меньше или равно d.

        int totalCount = 0;

        for (int i = 1; i <= d; i++)

            totalCount += findCount(i);

      

        return totalCount;

    }

      

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

    public static void main(String args[])

    {

        int d = 1;

        System.out.println(findCountUpto(d));

      

        d = 2;

        System.out.println( findCountUpto(d) );

      

        d = 4;

        System.out.println(findCountUpto(d));

    }

}

  

  
/ * Этот код предоставлен Никитой Тивари. * /

python3

# Программа Python 3 для поиска
# количество натуральных чисел до
# заданное количество цифр, которые
# содержит хотя бы один ноль

import math

  

  
# Сервисная функция для расчета
# количество натуральных чисел
# до заданного количества цифр
# которые содержат хотя бы один ноль

def findCountUpto(d) :

    # Сумма двух серий GP

    GP1_Sum = 9*((int)((math.pow(10,d))-1)//9)

    GP2_Sum = 9*((int)((math.pow(9,d))-1)//8)

   

    return GP1_Sum - GP2_Sum

  

  
Код водителя

d = 1

print(findCountUpto(d))

  

d = 2

print(findCountUpto(d))

  

d = 4

print(findCountUpto(d))

  

  
# Этот код предоставлен Никитой Тивари.

C #

// C # программа для поиска количества
// положительное целое число от активного числа
// из цифр, содержащих по крайней мере
// один ноль

using System;

  

class GFG {

      

    // Возвращает количество цифр 'd'

    // целые числа имеют цифру 0

    static int findCount(int d)

    {

        return 9 * (int)((Math.Pow(10, d - 1) 

                        - Math.Pow(9, d - 1)));

    }

      

    // полезная функция для подсчета

    // требуемый ответ

    static int findCountUpto(int d)

    {

        // Количество чисел с цифрами

        // меньше или равно d.

        int totalCount = 0;

        for (int i = 1; i <= d; i++)

            totalCount += findCount(i);

      

        return totalCount;

    }

      

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

    public static void Main()

    {

        int d = 1;

        Console.WriteLine(findCountUpto(d));

      

        d = 2;

        Console.WriteLine( findCountUpto(d) );

      

        d = 4;

        Console.WriteLine(findCountUpto(d));

    }

}

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

PHP

<?php
// PHP программа для поиска счета
// положительного целого числа данного
// количество цифр, содержащих
// по крайней мере один ноль

  
// Возвращает количество цифр 'd'
// целые числа имеют цифру 0

function findCount($d)

{

    return 9 * (pow(10, $d - 1) - 

                 pow(9, $d - 1));

}

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

function findCountUpto($d)

{

      

    // Подсчет чисел с

    // цифры меньше чем

    // или равно d.

    $totalCount = 0;

    for ($i = 1; $i <= $d; $i++)

        $totalCount += findCount($i);

  

    return $totalCount;

}

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

    $d = 1;

    echo findCountUpto($d),"\n" ;

  

    $d = 2;

    echo findCountUpto($d),"\n" ;

  

    $d = 4;

    echo findCountUpto($d) ;

    return 0;

}

  
// Этот код предоставлен нитин митталь.
?>

Выход :

0
9
2619 

Сложность времени: O (d)
Вспомогательное пространство: O (1)

Можем ли мы сделать решение более эффективным?
Да, если мы посмотрим ближе, требуемый ответ получен с использованием суммы следующих двух геометрических прогрессий:

i'th term of G.P. 1 = 9*10i - 1  where 1 <= i <= d
i'th term of G.P. 2 = 9*9i - 1 where 1 <= i <= d
The final answer is nothing but,

   
Sum of G.P 1 = 9*(10d - 1)/(10-1) 
             = 9*(10d - 1)/9
Similarly,
Sum of G.P 2 = 9*(9d - 1)/(9-1) 
             = 9*(9d - 1)/8
Using the above facts, we can optimize the solution to run in O(1) 

Ниже приведена эффективная программа для того же.

C ++

// C ++ программа для поиска количества натуральных чисел до
// заданное количество цифр, содержащих как минимум один ноль
#include<bits/stdc++.h>

using namespace std;

  
// Полезная функция для вычисления количества натуральных чисел
// до заданного числа цифр, которые содержат как минимум один ноль

int findCountUpto(int d)

{

    // Сумма двух серий GP

    int GP1_Sum = 9*((pow(10,d)-1)/9);

    int GP2_Sum = 9*((pow(9,d)-1)/8);

  

    return GP1_Sum - GP2_Sum;

}

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

int main()

{

    int d = 1;

    cout << findCountUpto(d) << endl;

  

    d = 2;

    cout << findCountUpto(d) << endl;

  

    d = 4;

    cout << findCountUpto(d) << endl;

    return 0;

}

Джава

// Java-программа для поиска количества
// натуральных чисел до
// заданное количество цифр
// которые содержат хотя бы один ноль

import java.io.*;

import java.math.*;

  

class GFG {

      

    // Сервисная функция для расчета

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

    // до заданного количества цифр

    // которые содержат хотя бы один ноль

    static int findCountUpto(int d)

    {

        // Сумма двух серий GP

        int GP1_Sum = 9 * ((int)((Math.pow(10, d)) - 1) / 9);

        int GP2_Sum = 9 * ((int)((Math.pow(9, d)) - 1) / 8);

      

        return GP1_Sum - GP2_Sum;

    }

      

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

    public static void main(String args[])

    {

        int d = 1;

        System.out.println(findCountUpto(d));

          

        d = 2;

        System.out.println(findCountUpto(d));

          

        d = 4;

        System.out.println(findCountUpto(d));

          

    }

}

  

  
/ * Этот код предоставлен Никитой Тивари. * /

python3

# Программа Python 3 для поиска
# количество положительных целых чисел
# заданное количество цифр, которые
# содержит хотя бы один ноль

import math

  
# Возвращает количество цифр 'd'
# целые числа имеют цифру 0

def findCount(d) :

    return 9*(pow(10,d-1) - pow(9,d-1));

  

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

def findCountUpto(d) :

  

    # Количество чисел с

    # цифры меньше чем

    # или равно d.

    totalCount = 0

    for i in range(1,d+1) :

        totalCount = totalCount + findCount(i)

   

    return totalCount

  

   
Код водителя

d = 1

print(findCountUpto(d))

  

d = 2

print(findCountUpto(d))

  

d = 4

print(findCountUpto(d))

  

  
# Этот код предоставлен Никитой Тивари.

C #

// C # программа для поиска количества
// натуральных чисел до
// заданное количество цифр
// которые содержат хотя бы один ноль

using System;

  

class GFG {

      

    // Сервисная функция для расчета

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

    // до заданного количества цифр

    // которые содержат хотя бы один ноль

    static int findCountUpto(int d)

    {

          

        // Сумма двух серий GP

        int GP1_Sum = 9 * ((int)((Math.Pow(10, 

                                d)) - 1) / 9);

        int GP2_Sum = 9 * ((int)((Math.Pow(9,

                                d)) - 1) / 8);

      

        return GP1_Sum - GP2_Sum;

    }

      

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

    public static void Main()

    {

        int d = 1;

        Console.WriteLine(findCountUpto(d));

          

        d = 2;

        Console.WriteLine(findCountUpto(d));

          

        d = 4;

        Console.WriteLine(findCountUpto(d));

          

    }

}

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

PHP

<?php
// PHP программа для поиска счета
// натуральных чисел до
// заданное количество цифр
// содержат хотя бы один ноль

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

function findCountUpto($d)

{

      

    // Сумма двух серий GP

    $GP1_Sum = 9 * ((pow(10, $d) - 1) / 9);

    $GP2_Sum = 9 * ((pow(9, $d) - 1) / 8);

  

    return $GP1_Sum - $GP2_Sum;

}

  

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

    $d = 1;

    echo findCountUpto($d),"\n";

  

    $d = 2;

    echo findCountUpto($d),"\n";

  

    $d = 4;

    echo findCountUpto($d) ,"\n";

      
// Этот код предоставлен anuj_67.
?>

Выход :

0
9
2619 

Сложность времени: O (1)
Вспомогательное пространство: O (1)

В следующем наборе мы увидим еще одну проблему повышенной сложности, которая может быть решена с использованием очень похожей техники.

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

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

Считать положительные целые числа с 0 в качестве цифры и максимальные цифры 'd'

0.00 (0%) 0 votes