计算以0为数字的数字-yiteyi-C++库

问题： 计算从1到N的整数中有多少个包含0作为数字。 例如：

null

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

本文讨论了一个简单的解决方案以前的职位本文讨论了一个优化的解决方案。让我们仔细分析一下这个问题。 让给定的数字有d位数。 可通过计算以下两个值来计算所需答案：

最大为d-1位的0位整数的计数。
0位整数的计数，正好有d位（当然小于/等于给定的数字！）

因此，解决方案将是上述两项的总和。第一部分已经讨论过了在这里 . 如何找到第二部分？ 我们可以找到具有d个数字（小于等于给定数字）的整数的总数，其中不包含任何零。为了找到这个，我们遍历数字，一次一个数字。我们发现非负整数的计数如下：

如果该位置的数字为零，则将计数器减量1并断开（因为我们无法进一步移动，减量以确保数字本身包含零）
否则，将（数字-1）乘以幂（9，数字右边的位数）

让我们用一个例子来说明。

Let the number be n = 123. non_zero = 0We encounter 1 first,  add (1-1)*9²  to non_zero (= 0+0)We encounter 2,  add (2-1)*9¹ to non_zero (= 0+9 = 9)We encounter 3,  add (3-1)*9⁰to non_zero (=9+3 = 12)

我们可以观察到，non_zero表示由3位数字（不大于123）组成的整数的数量，并且不包含任何零。i、（111、112、…、119、121、122、123）（建议验证一次）现在，有人可能会问，计算没有零的数字的计数有什么意义？ 对的我们感兴趣的是找到零整数的计数。 然而，我们现在可以很容易地发现，在忽略最重要的位置后，通过从n中减去非0。i、例如，在我们前面的例子中，零=23–非_零=23-12=11，最后我们添加这两部分以得到所需的结果！！下面是上述想法的实现。

C++

                         //Modified C++ program to count number from 1 to n with                       
                         // 0 as a digit.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns count of integers having zero upto given digits                       
                         int                                     zeroUpto(                                     int                                     digits)                       
                         {                       
                                                 // Refer below article for details                       
                                                 //                           https://www.geeksforgeeks.org/count-positive-integers-0-digit/                                    
                                                 int                                     first = (                                     pow                                     (10,digits)-1)/9;                       
                                                 int                                     second = (                                     pow                                     (9,digits)-1)/8;                       
                                                 return                                     9 * (first - second);                       
                         }                       
           
                         // utility function to convert character representation                       
                         // to integer                       
                         int                                     toInt(                                     char                                     c)                       
                         {                       
                                                 return                                     int                                     (c)-48;                       
                         }                       
           
                         // counts numbers having zero as digits upto a given                       
                         // number 'num'                       
                         int                                     countZero(string num)                       
                         {                       
                                                 // k denoted the number of digits in the number                       
                                                 int                                     k = num.length();                       
           
                                                 // Calculating the total number having zeros,                       
                                                 // which upto k-1 digits                       
                                                 int                                     total = zeroUpto(k-1);                       
           
                                                 // Now let us calculate the numbers which don't have                       
                                                 // any zeros. In that k digits upto the given number                       
                                                 int                                     non_zero = 0;                       
                                                 for                                     (                                     int                                     i=0; i<num.length(); i++)                       
                                                 {                       
                                                 // If the number itself contains a zero then                       
                                                 // decrement the counter                       
                                                 if                                     (num[i] ==                                     '0'                                     )                       
                                                 {                       
                                                 non_zero--;                       
                                                 break                                     ;                       
                                                 }                       
           
                                                 // Adding the number of non zero numbers that                       
                                                 // can be formed                       
                                                 non_zero += (toInt(num[i])-1) * (                                     pow                                     (9,k-1-i));                       
                                                 }                       
           
                                                 int                                     no = 0, remaining = 0,calculatedUpto=0;                       
           
                                                 // Calculate the number and the remaining after                       
                                                 // ignoring the most significant digit                       
                                                 for                                     (                                     int                                     i=0; i<num.length(); i++)                       
                                                 {                       
                                                 no = no*10 + (toInt(num[i]));                       
                                                 if                                     (i != 0)                       
                                                 calculatedUpto = calculatedUpto*10 + 9;                       
                                                 }                       
                                                 remaining = no-calculatedUpto;                       
           
                                                 // Final answer is calculated                       
                                                 // It is calculated by subtracting 9....9 (d-1) times                       
                                                 // from no.                       
                                                 int                                     ans = zeroUpto(k-1) + (remaining-non_zero-1);                       
                                                 return                                     ans;                       
                         }                       
           
                         // Driver program to test the above functions                       
                         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

                         //Modified Java program to count number from 1 to n with                       
                         // 0 as a digit.                       
           
                         public                                     class                                     GFG {                       
           
           
                         // Returns count of integers having zero upto given digits                       
                         static                                     int                                     zeroUpto(                                     int                                     digits)                       
                         {                       
                                                 // Refer below article for details                       
                                                 //                           https://www.geeksforgeeks.org/count-positive-integers-0-digit/                                    
                                                 int                                     first = (                                     int                                     ) ((Math.pow(                                     10                                     ,digits)-                                     1                                     )/                                     9                                     );                       
                                                 int                                     second = (                                     int                                     ) ((Math.pow(                                     9                                     ,digits)-                                     1                                     )/                                     8                                     );                       
                                                 return                                     9                                     * (first - second);                       
                         }                       
                                   
                         // utility function to convert character representation                       
                         // to integer                       
                         static                                     int                                     toInt(                                     char                                     c)                       
                         {                       
                                                 return                                     (                                     int                                     )(c)-                                     48                                     ;                       
                         }                       
                                   
                         // counts numbers having zero as digits upto a given                       
                         // number 'num'                       
                         static                                     int                                     countZero(String num)                       
                         {                       
                                                 // k denoted the number of digits in the number                       
                                                 int                                     k = num.length();                       
                                   
                                                 // Calculating the total number having zeros,                       
                                                 // which upto k-1 digits                       
                                                 int                                     total = zeroUpto(k-                                     1                                     );                       
                                   
                                                 // Now let us calculate the numbers which don't have                       
                                                 // any zeros. In that k digits upto the given number                       
                                                 int                                     non_zero =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i=                                     0                                     ; i<num.length(); i++)                       
                                                 {                       
                                                 // If the number itself contains a zero then                       
                                                 // decrement the counter                       
                                                 if                                     (num.charAt(i) ==                                     '0'                                     )                       
                                                 {                       
                                                 non_zero--;                       
                                                 break                                     ;                       
                                                 }                       
                                   
                                                 // Adding the number of non zero numbers that                       
                                                 // can be formed                       
                                                 non_zero += (toInt(num.charAt(i))-                                     1                                     ) * (Math.pow(                                     9                                     ,k-                                     1                                     -i));                       
                                                 }                       
                                   
                                                 int                                     no =                                     0                                     , remaining =                                     0                                     ,calculatedUpto=                                     0                                     ;                       
                                   
                                                 // Calculate the number and the remaining after                       
                                                 // ignoring the most significant digit                       
                                                 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;                       
                                   
                                                 // Final answer is calculated                       
                                                 // It is calculated by subtracting 9....9 (d-1) times                       
                                                 // from no.                       
                                                 int                                     ans = zeroUpto(k-                                     1                                     ) + (remaining-non_zero-                                     1                                     );                       
                                                 return                                     ans;                       
                         }                       
                                   
                         // Driver program to test the above functions                       
           
                                                 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));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by 29AjayKumar                       

Python3

                         # Python3 program to count number from 1 to n                       
                         # with 0 as a digit.                       
           
                         # Returns count of integers having zero                       
                         # upto given digits                       
                         def                                     zeroUpto(digits):                       
                                   
                                                 first                                     =                                     int                                     ((                                     pow                                     (                                     10                                     , digits)                                     -                                     1                                     )                                     /                                     9                                     );                       
                                                 second                                     =                                     int                                     ((                                     pow                                     (                                     9                                     , digits)                                     -                                     1                                     )                                     /                                     8                                     );                       
                                                 return                                     9                                     *                                     (first                                     -                                     second);                       
           
                         # counts numbers having zero as digits                       
                         # upto a given number 'num'                       
                         def                                     countZero(num):                       
                                   
                                                 # k denoted the number of digits                       
                                                 # in the number                       
                                                 k                                     =                                     len                                     (num);                       
           
                                                 # Calculating the total number having                       
                                                 # zeros, which upto k-1 digits                       
                                                 total                                     =                                     zeroUpto(k                                     -                                     1                                     );                       
           
                                                 # Now let us calculate the numbers which                       
                                                 # don't have any zeros. In that k digits                       
                                                 # upto the given number                       
                                                 non_zero                                     =                                     0                                     ;                       
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (num)):                       
                                   
                                                 # If the number itself contains a zero                       
                                                 # then decrement the counter                       
                                                 if                                     (num[i]                                     =                                     =                                     '0'                                     ):                       
                                                 non_zero                                     -                                     =                                     1                                     ;                       
                                                 break                                     ;                       
           
                                                 # Adding the number of non zero numbers                       
                                                 # that can be formed                       
                                                 non_zero                                     +                                     =                                     (((                                     ord                                     (num[i])                                     -                                     ord                                     (                                     '0'                                     ))                                     -                                     1                                     )                                     *                       
                                                 (                                     pow                                     (                                     9                                     , k                                     -                                     1                                     -                                     i)));                       
           
                                                 no                                     =                                     0                                     ;                       
                                                 remaining                                     =                                     0                                     ;                       
                                                 calculatedUpto                                     =                                     0                                     ;                       
           
                                                 # Calculate the number and the remaining                       
                                                 # after ignoring the most significant digit                       
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (num)):                       
                                                 no                                     =                                     no                                     *                                     10                                     +                                     (                                     ord                                     (num[i])                                     -                                     ord                                     (                                     '0'                                     ));                       
                                                 if                                     (i !                                     =                                     0                                     ):                       
                                                 calculatedUpto                                     =                                     calculatedUpto                                     *                                     10                                     +                                     9                                     ;                       
                                   
                                                 remaining                                     =                                     no                                     -                                     calculatedUpto;                       
           
                                                 # Final answer is calculated. It is calculated                       
                                                 # by subtracting 9....9 (d-1) times from no.                       
                                                 ans                                     =                                     zeroUpto(k                                     -                                     1                                     )                                     +                                     (remaining                                     -                                     non_zero                                     -                                     1                                     );                       
                                                 return                                     ans;                       
           
                         # Driver Code                       
                         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));                       
           
                         # This code is contributed by mits                       

C#

                         // Modified C# program to count number from 1 to n with                       
                         // 0 as a digit.                       
           
                         using                                     System;                       
                         public                                     class                                     GFG{                       
           
                         // Returns count of integers having zero upto given digits                       
                         static                                     int                                     zeroUpto(                                     int                                     digits)                       
                         {                       
                                                 // Refer below article for details                       
                                                 //                           https://www.geeksforgeeks.org/count-positive-integers-0-digit/                                    
                                                 int                                     first = (                                     int                                     ) ((Math.Pow(10,digits)-1)/9);                       
                                                 int                                     second = (                                     int                                     ) ((Math.Pow(9,digits)-1)/8);                       
                                                 return                                     9 * (first - second);                       
                         }                       
           
                         // utility function to convert character representation                       
                         // to integer                       
                         static                                     int                                     toInt(                                     char                                     c)                       
                         {                       
                                                 return                                     (                                     int                                     )(c)-48;                       
                         }                       
           
                         // counts numbers having zero as digits upto a given                       
                         // number 'num'                       
                         static                                     int                                     countZero(String num)                       
                         {                       
                                                 // k denoted the number of digits in the number                       
                                                 int                                     k = num.Length;                       
           
                                                 // Calculating the total number having zeros,                       
                                                 // which upto k-1 digits                       
                                                 int                                     total = zeroUpto(k-1);                       
           
                                                 // Now let us calculate the numbers which don't have                       
                                                 // any zeros. In that k digits upto the given number                       
                                                 int                                     non_zero = 0;                       
                                                 for                                     (                                     int                                     i=0; i<num.Length; i++)                       
                                                 {                       
                                                 // If the number itself contains a zero then                       
                                                 // decrement the counter                       
                                                 if                                     (num[i] ==                                     '0'                                     )                       
                                                 {                       
                                                 non_zero--;                       
                                                 break                                     ;                       
                                                 }                       
           
                                                 // Adding the number of non zero numbers that                       
                                                 // can be formed                       
                                                 non_zero += (toInt(num[i])-1) * (                                     int                                     )(Math.Pow(9,k-1-i));                       
                                                 }                       
           
                                                 int                                     no = 0, remaining = 0,calculatedUpto=0;                       
           
                                                 // Calculate the number and the remaining after                       
                                                 // ignoring the most significant digit                       
                                                 for                                     (                                     int                                     i=0; i<num.Length; i++)                       
                                                 {                       
                                                 no = no*10 + (toInt(num[i]));                       
                                                 if                                     (i != 0)                       
                                                 calculatedUpto = calculatedUpto*10 + 9;                       
                                                 }                       
                                                 remaining = no-calculatedUpto;                       
           
                                                 // Final answer is calculated                       
                                                 // It is calculated by subtracting 9....9 (d-1) times                       
                                                 // from no.                       
                                                 int                                     ans = zeroUpto(k-1) + (remaining-non_zero-1);                       
                                                 return                                     ans;                       
                         }                       
           
                         // Driver program to test the above functions                       
           
                                                 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));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by 29AjayKumar                       

PHP

                         <?php                       
                         // PHP program to count                       
                         // number from 1 to n                       
                         // with 0 as a digit.                       
           
                         // Returns count of integers                       
                         // having zero upto given digits                       
                         function                                     zeroUpto(                                     $digits                                     )                       
                         {                       
                                   
                                                 $first                                     = (int)((pow(10,                       
                                                 $digits                                     ) - 1) / 9);                       
                                                 $second                                     = (int)((pow(9,                       
                                                 $digits                                     ) - 1) / 8);                       
                                                 return                                     9 * (                                     $first                                     -                                     $second                                     );                       
                         }                       
           
           
                         // counts numbers having                       
                         // zero as digits upto a                       
                         // given number 'num'                       
                         function                                     countZero(                                     $num                                     )                       
                         {                       
                                                 // k denoted the number                       
                                                 // of digits in the number                       
                                                 $k                                     =                                     strlen                                     (                                     $num                                     );                       
           
                                                 // Calculating the total                       
                                                 // number having zeros,                       
                                                 // which upto k-1 digits                       
                                                 $total                                     = zeroUpto(                                     $k                                     -1);                       
           
                                                 // Now let us calculate                       
                                                 // the numbers which don't                       
                                                 // have any zeros. In that                       
                                                 // k digits upto the given                       
                                                 // number                       
                                                 $non_zero                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0;                       
                                                 $i                                     <                                     strlen                                     (                                     $num                                     );                                     $i                                     ++)                       
                                                 {                       
                                                 // If the number itself                       
                                                 // contains a zero then                       
                                                 // decrement the counter                       
                                                 if                                     (                                     $num                                     [                                     $i                                     ] ==                                     '0'                                     )                       
                                                 {                       
                                                 $non_zero                                     --;                       
                                                 break                                     ;                       
                                                 }                       
           
                                                 // Adding the number of                       
                                                 // non zero numbers that                       
                                                 // can be formed                       
                                                 $non_zero                                     += ((                                     $num                                     [                                     $i                                     ] -                                     '0'                                     ) - 1) *                       
                                                 (pow(9,                                     $k                                     - 1 -                                     $i                                     ));                       
                                                 }                       
           
                                                 $no                                     = 0;                       
                                                 $remaining                                     = 0;                       
                                                 $calculatedUpto                                     = 0;                       
           
                                                 // Calculate the number                       
                                                 // and the remaining after                       
                                                 // ignoring the most                       
                                                 // significant digit                       
                                                 for                                     (                                     $i                                     = 0;                       
                                                 $i                                     <                                     strlen                                     (                                     $num                                     );                                     $i                                     ++)                       
                                                 {                       
                                                 $no                                     =                                     $no                                     * 10 + (                                     $num                                     [                                     $i                                     ] -                                     '0'                                     );                       
                                                 if                                     (                                     $i                                     != 0)                       
                                                 $calculatedUpto                                     =                                     $calculatedUpto                                     *                       
                                                 10 + 9;                       
                                                 }                       
                                   
                                                 $remaining                                     =                                     $no                                     -                                     $calculatedUpto                                     ;                       
           
                                                 // Final answer is calculated                       
                                                 // It is calculated by subtracting                       
                                                 // 9....9 (d-1) times from no.                       
                                                 $ans                                     = zeroUpto(                                     $k                                     - 1) +                       
                                                 (                                     $remaining                                     -                       
                                                 $non_zero                                     - 1);                       
                                                 return                                     $ans                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $num                                     =                                     "107"                                     ;                       
                         echo                                     "Count of numbers from 1 to "                                     .                       
                                                 $num                                     .                                     " is "                                     .                       
                                                 countZero(                                     $num                                     ) .                                     ""                                     ;                       
           
                         $num                                     =                                     "1264"                                     ;                       
                         echo                                     "Count of numbers from 1 to "                                     .                       
                                                 $num                                     .                                     " is "                                     .                       
                                                 countZero(                                     $num                                     );                       
           
                         // This code is contributed                       
                         // by mits                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Modified javascript program to count number from 1 to n with                       
                         // 0 as a digit.                       
           
                         // Returns count of integers having zero upto given digits                       
                         function                                     zeroUpto(digits)                       
                         {                       
           
                                                 // Refer below article for details                       
                                                 //                           https://www.geeksforgeeks.org/count-positive-integers-0-digit/                                    
                                                 var                                     first = parseInt( ((Math.pow(10,digits)-1)/9));                       
                                                 var                                     second = parseInt( ((Math.pow(9,digits)-1)/8));                       
                                                 return                                     9 * (first - second);                       
                         }                       
                                   
                         // utility function to convert character representation                       
                         // to integer                       
                         function                                     toInt(c)                       
                         {                       
                                                 return                                     parseInt((c.charCodeAt(0))-48);                       
                         }                       
                                   
                         // counts numbers having zero as digits upto a given                       
                         // number 'num'                       
                         function                                     countZero(num)                       
                         {                       
                                                 // k denoted the number of digits in the number                       
                                                 var                                     k = num.length;                       
                                   
                                                 // Calculating the total number having zeros,                       
                                                 // which upto k-1 digits                       
                                                 var                                     total = zeroUpto(k-1);                       
                                   
                                                 // Now let us calculate the numbers which don't have                       
                                                 // any zeros. In that k digits upto the given number                       
                                                 var                                     non_zero = 0;                       
                                                 for                                     (i=0; i<num.length; i++)                       
                                                 {                       
                                                 // If the number itself contains a zero then                       
                                                 // decrement the counter                       
                                                 if                                     (num.charAt(i) == '0')                       
                                                 {                       
                                                 non_zero--;                       
                                                 break                                     ;                       
                                                 }                       
                                   
                                                 // Adding the number of non zero numbers that                       
                                                 // can be formed                       
                                                 non_zero += (toInt(num.charAt(i))-1) * (Math.pow(9,k-1-i));                       
                                                 }                       
                                   
                                                 var                                     no = 0, remaining = 0,calculatedUpto=0;                       
                                   
                                                 // Calculate the number and the remaining after                       
                                                 // ignoring the most significant digit                       
                                                 for                                     (i=0; i<num.length; i++)                       
                                                 {                       
                                                 no = no*10 + (toInt(num.charAt(i)));                       
                                                 if                                     (i != 0)                       
                                                 calculatedUpto = calculatedUpto*10 + 9;                       
                                                 }                       
                                                 remaining = no-calculatedUpto;                       
                                   
                                                 // Final answer is calculated                       
                                                 // It is calculated by subtracting 9....9 (d-1) times                       
                                                 // from no.                       
                                                 var                                     ans = zeroUpto(k-1) + (remaining-non_zero-1);                       
                                                 return                                     ans;                       
                         }                       
                                   
                         // Driver program to test the above functions                       
                         var                                     num =                                     "107"                                     ;                       
                         document.write(                                     "Count of numbers from 1"                                     +                                     " to "                       
                                                 + num +                                     " is "                                     + countZero(num));                       
           
                         var                                     num =                                     "1264"                                     ;                       
                         document.write(                                     "<br>Count of numbers from 1"                                     +                                     " to "                       
                                                 + num +                                     " is "                                     +countZero(num));                       
           
                         // This code is contributed by shikhasingrajput                       
                         </script>                       

输出：

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

复杂性分析： 时间复杂性： O（d），在哪里 d是数字的数量，即O（对数n） 辅助空间：O（1）

本文由阿什图什·库马尔 .如果你喜欢GeekSforgek，并且想贡献自己的力量，你也可以写一篇文章，并将文章邮寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章