树的质心分解-yiteyi-C++库

给定一个数字d，表示一个数字的位数。求至少有一个零且由d或更少数字组成的正整数的总数。

null

Examples:Input : d = 1Output : 0There's no natural number of 1 digit that contains a zero.Input : d = 2Output : 9Input : d = 3Output : 180For 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.

我们强烈建议您在继续解决方案之前单击此处并进行练习。

这主要是下文的延伸。以0为数字计算“d”位正整数。如果我们仔细观察，这个问题与我们在第一组中讨论的问题非常相似。对于给定的d，如果我们找到由数字1、2、3…组成的0，我们可以得到所需的答案…。。，d、最后，我们可以添加它们以获得输出。下面是同样的程序。

C++

                         // C++ program to find the count of positive integer of a                       
                         // given number of digits that contain atleast one zero                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns count of 'd' digit integers have 0 as a digit                       
                         int                                     findCount(                                     int                                     d)                       
                         {                       
                                                 return                                     9*(                                     pow                                     (10,d-1) -                                     pow                                     (9,d-1));                       
                         }                       
           
                         // utility function to count the required answer                       
                         int                                     findCountUpto(                                     int                                     d)                       
                         {                       
                                                 // Count of numbers with digits smaller than                       
                                                 // or equal to d.                       
                                                 int                                     totalCount = 0;                       
                                                 for                                     (                                     int                                     i=1; i<=d; i++)                       
                                                 totalCount += findCount(i);                       
           
                                                 return                                     totalCount;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     d = 1;                       
                                                 cout << findCountUpto(d) << endl;                       
           
                                                 d = 2;                       
                                                 cout << findCountUpto(d) << endl;                       
           
                                                 d = 4;                       
                                                 cout << findCountUpto(d) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find the count of                       
                         // positive integer of agiven number                       
                         // of digits that contain atleast one zero                       
                         import                                     java.io.*;                       
                         import                                     java.math.*;                       
           
                         class                                     GFG {                       
                                   
                                                 // Returns count of 'd' digit                       
                                                 // integers have 0 as a digit                       
                                                 static                                     int                                     findCount(                                     int                                     d)                       
                                                 {                       
                                                 return                                     9                                     * (                                     int                                     )((Math.pow(                                     10                                     , d -                                     1                                     )                       
                                                 - Math.pow(                                     9                                     , d -                                     1                                     )));                       
                                                 }                       
                                   
                                                 // utility function to count                       
                                                 // the required answer                       
                                                 static                                     int                                     findCountUpto(                                     int                                     d)                       
                                                 {                       
                                                 // Count of numbers with digits                       
                                                 // smaller than or equal to d.                       
                                                 int                                     totalCount =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= d; i++)                       
                                                 totalCount += findCount(i);                       
                                   
                                                 return                                     totalCount;                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 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));                       
                                                 }                       
                         }                       
           
           
                         /*This code is contributed by Nikita Tiwari.*/                       

Python3

                         # Python 3 program to find the                       
                         # count of natural numbers upto a                       
                         # given number of digits that                       
                         # contain atleast one zero                       
                         import                                     math                       
           
           
                         # Utility function to calculate                       
                         # the count of natural numbers                       
                         # upto a given number of digits                       
                         # that contain atleast one zero                       
                         def                                     findCountUpto(d) :                       
                                                 # Sum of two GP series                       
                                                 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                       
           
           
                         # Driver Code                       
                         d                                     =                                     1                       
                         print                                     (findCountUpto(d))                       
           
                         d                                     =                                     2                       
                         print                                     (findCountUpto(d))                       
           
                         d                                     =                                     4                       
                         print                                     (findCountUpto(d))                       
           
           
                         # This code is contributed by Nikita Tiwari.                       

C#

                         // C# program to find the count of                       
                         // positive integer of agiven number                       
                         // of digits that contain atleast                       
                         // one zero                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // Returns count of 'd' digit                       
                                                 // integers have 0 as a digit                       
                                                 static                                     int                                     findCount(                                     int                                     d)                       
                                                 {                       
                                                 return                                     9 * (                                     int                                     )((Math.Pow(10, d - 1)                       
                                                 - Math.Pow(9, d - 1)));                       
                                                 }                       
                                   
                                                 // utility function to count                       
                                                 // the required answer                       
                                                 static                                     int                                     findCountUpto(                                     int                                     d)                       
                                                 {                       
                                                 // Count of numbers with digits                       
                                                 // smaller than or equal to d.                       
                                                 int                                     totalCount = 0;                       
                                                 for                                     (                                     int                                     i = 1; i <= d; i++)                       
                                                 totalCount += findCount(i);                       
                                   
                                                 return                                     totalCount;                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     d = 1;                       
                                                 Console.WriteLine(findCountUpto(d));                       
                                   
                                                 d = 2;                       
                                                 Console.WriteLine( findCountUpto(d) );                       
                                   
                                                 d = 4;                       
                                                 Console.WriteLine(findCountUpto(d));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007                       

PHP

                         <?php                       
                         // PHP program to find the count                       
                         // of positive integer of a given                       
                         // number of digits that contain                       
                         // atleast one zero                       
           
                         // Returns count of 'd' digit                       
                         // integers have 0 as a digit                       
                         function                                     findCount(                                     $d                                     )                       
                         {                       
                                                 return                                     9 * (pow(10,                                     $d                                     - 1) -                       
                                                 pow(9,                                     $d                                     - 1));                       
                         }                       
           
                         // function to count                       
                         // the required answer                       
                         function                                     findCountUpto(                                     $d                                     )                       
                         {                       
                                   
                                                 // Count of numbers with                       
                                                 // digits smaller than                       
                                                 // or equal to d.                       
                                                 $totalCount                                     = 0;                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $d                                     ;                                     $i                                     ++)                       
                                                 $totalCount                                     += findCount(                                     $i                                     );                       
           
                                                 return                                     $totalCount                                     ;                       
                         }                       
           
                         // Driver Code                       
                         {                       
                                                 $d                                     = 1;                       
                                                 echo                                     findCountUpto(                                     $d                                     ),                                     ""                                     ;                       
           
                                                 $d                                     = 2;                       
                                                 echo                                     findCountUpto(                                     $d                                     ),                                     ""                                     ;                       
           
                                                 $d                                     = 4;                       
                                                 echo                                     findCountUpto(                                     $d                                     ) ;                       
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by nitin mittal.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to find the count of                       
                         // positive integer of agiven number                       
                         // of digits that contain atleast one zero                       
           
                                                 // Returns count of 'd' digit                       
                                                 // integers have 0 as a digit                       
                                                 function                                     findCount(d)                       
                                                 {                       
                                                 return                                     9 * ((Math.pow(10, d - 1)                       
                                                 - Math.pow(9, d - 1)));                       
                                                 }                       
                                   
                                                 // utility function to count                       
                                                 // the required answer                       
                                                 function                                     findCountUpto(d)                       
                                                 {                       
                                                 // Count of numbers with digits                       
                                                 // smaller than or equal to d.                       
                                                 let totalCount = 0;                       
                                                 for                                     (let i = 1; i <= d; i++)                       
                                                 totalCount += findCount(i);                       
                                   
                                                 return                                     totalCount;                       
                                                 }                       
           
                         // Driver Code                       
           
                                                 let d = 1;                       
                                                 document.write(findCountUpto(d) +                                     "<br/>"                                     );                       
                                   
                                                 d = 2;                       
                                                 document.write( findCountUpto(d) +                                     "<br/>"                                     );                       
                                   
                                                 d = 4;                       
                                                 document.write(findCountUpto(d) +                                     "<br/>"                                     );                       
                                   
                                                 // This code is contributed by target_2.                       
                         </script>                       

输出：

时间复杂度：O（d）辅助空间：O（1） 我们能提高解决方案的效率吗？ 是的，如果我们仔细观察，所需的答案是使用以下两个几何级数之和得到的：

i'th term of G.P. 1 = 9*10ⁱ - 1  where 1 <= i <= di'th term of G.P. 2 = 9*9ⁱ - 1 where 1 <= i <= dThe final answer is nothing but,Sum of G.P 1 = 9*(10^d - 1)/(10-1) = 9*(10^d - 1)/9Similarly,Sum of G.P 2 = 9*(9^d - 1)/(9-1) = 9*(9^d - 1)/8Using the above facts, we can optimize the solution to run in O(1)

下面是一个同样有效的程序。

C++

                         // C++ program to find the count of natural numbers upto a                       
                         // given number of digits that contain atleast one zero                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Utility function to calculate the count of natural numbers                       
                         // upto a given number of digits that contain atleast one zero                       
                         int                                     findCountUpto(                                     int                                     d)                       
                         {                       
                                                 // Sum of two GP series                       
                                                 int                                     GP1_Sum = 9*((                                     pow                                     (10,d)-1)/9);                       
                                                 int                                     GP2_Sum = 9*((                                     pow                                     (9,d)-1)/8);                       
           
                                                 return                                     GP1_Sum - GP2_Sum;                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     d = 1;                       
                                                 cout << findCountUpto(d) << endl;                       
           
                                                 d = 2;                       
                                                 cout << findCountUpto(d) << endl;                       
           
                                                 d = 4;                       
                                                 cout << findCountUpto(d) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find the count                       
                         // of natural numbers upto a                       
                         // given number of digits                       
                         // that contain atleast one zero                       
                         import                                     java.io.*;                       
                         import                                     java.math.*;                       
           
                         class                                     GFG {                       
                                   
                                                 // Utility function to calculate                       
                                                 // the count of natural numbers                       
                                                 // upto a given number of digits                       
                                                 // that contain atleast one zero                       
                                                 static                                     int                                     findCountUpto(                                     int                                     d)                       
                                                 {                       
                                                 // Sum of two GP series                       
                                                 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;                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 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));                       
                                   
                                                 }                       
                         }                       
           
           
                         /* This code is contributed by Nikita Tiwari.*/                       

Python3

                         # Python 3 program to find the                       
                         # count of positive integer of a                       
                         # given number of digits that                       
                         # contain atleast one zero                       
                         import                                     math                       
           
                         # Returns count of 'd' digit                       
                         # integers have 0 as a digit                       
                         def                                     findCount(d) :                       
                                                 return                                     9                                     *                                     (                                     pow                                     (                                     10                                     ,d                                     -                                     1                                     )                                     -                                     pow                                     (                                     9                                     ,d                                     -                                     1                                     ));                       
           
           
                         # utility function to count                       
                         # the required answer                       
                         def                                     findCountUpto(d) :                       
           
                                                 # Count of numbers with                       
                                                 # digits smaller than                       
                                                 # or equal to d.                       
                                                 totalCount                                     =                                     0                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     ,d                                     +                                     1                                     ) :                       
                                                 totalCount                                     =                                     totalCount                                     +                                     findCount(i)                       
                                   
                                                 return                                     totalCount                       
           
                                   
                         # Driver Code                       
                         d                                     =                                     1                       
                         print                                     (findCountUpto(d))                       
           
                         d                                     =                                     2                       
                         print                                     (findCountUpto(d))                       
           
                         d                                     =                                     4                       
                         print                                     (findCountUpto(d))                       
           
           
                         # This code is contributed by Nikita Tiwari.                       

C#

                         // C# program to find the count                       
                         // of natural numbers upto a                       
                         // given number of digits                       
                         // that contain atleast one zero                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // Utility function to calculate                       
                                                 // the count of natural numbers                       
                                                 // upto a given number of digits                       
                                                 // that contain atleast one zero                       
                                                 static                                     int                                     findCountUpto(                                     int                                     d)                       
                                                 {                       
                                   
                                                 // Sum of two GP series                       
                                                 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;                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     d = 1;                       
                                                 Console.WriteLine(findCountUpto(d));                       
                                   
                                                 d = 2;                       
                                                 Console.WriteLine(findCountUpto(d));                       
                                   
                                                 d = 4;                       
                                                 Console.WriteLine(findCountUpto(d));                       
                                   
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007                       

PHP

                         <?php                       
                         // PHP program to find the count                       
                         // of natural numbers upto a                       
                         // given number of digits that                       
                         // contain atleast one zero                       
           
                         // function to calculate the                       
                         // count of natural numbers                       
                         // upto a given number of digits                       
                         // that contain atleast one zero                       
                         function                                     findCountUpto(                                     $d                                     )                       
                         {                       
                                   
                                                 // Sum of two GP series                       
                                                 $GP1_Sum                                     = 9 * ((pow(10,                                     $d                                     ) - 1) / 9);                       
                                                 $GP2_Sum                                     = 9 * ((pow(9,                                     $d                                     ) - 1) / 8);                       
           
                                                 return                                     $GP1_Sum                                     -                                     $GP2_Sum                                     ;                       
                         }                       
           
                                                 // Driver Code                       
                                                 $d                                     = 1;                       
                                                 echo                                     findCountUpto(                                     $d                                     ),                                     ""                                     ;                       
           
                                                 $d                                     = 2;                       
                                                 echo                                     findCountUpto(                                     $d                                     ),                                     ""                                     ;                       
           
                                                 $d                                     = 4;                       
                                                 echo                                     findCountUpto(                                     $d                                     ) ,                                     ""                                     ;                       
                                   
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         // Javascript program to find the count                       
                         // of natural numbers upto a                       
                         // given number of digits that                       
                         // contain atleast one zero                       
           
                         // function to calculate the                       
                         // count of natural numbers                       
                         // upto a given number of digits                       
                         // that contain atleast one zero                       
                         function                                     findCountUpto(d)                       
                         {                       
                                   
                                                 // Sum of two GP series                       
                                                 let GP1_Sum = 9 * ((Math.pow(10, d) - 1) / 9);                       
                                                 let GP2_Sum = 9 * ((Math.pow(9, d) - 1) / 8);                       
           
                                                 return                                     GP1_Sum - GP2_Sum;                       
                         }                       
           
                                                 // Driver Code                       
                                                 let d = 1;                       
                                                 document.write(findCountUpto(d) +                                     "<br>"                                     );                       
           
                                                 d = 2;                       
                                                 document.write(findCountUpto(d) +                                     "<br>"                                     );                       
           
                                                 d = 4;                       
                                                 document.write(findCountUpto(d)  +                                     "<br>"                                     );                       
                                   
                         // This code is contributed by _saurabh_jaiswal.                       

输出：

时间复杂度：O（1）辅助空间：O（1）在下一集中，我们将看到另一个难度增加的问题，可以使用非常类似的技术来解决。

本文由阿什图什·库马尔。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。

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

THE END

技术文章