数量为1的总数-yiteyi-C++库

给定一个整数n，计算所有小于或等于n的正整数中出现的数字1的总数。 例如：

null

Input : n = 13Output : 6Explanation:Here, no <= 13 containing 1 are 1, 10, 11,12, 13. So, total 1s are 6.Input : n = 5Output : 1Here, no <= 13 containing 1 are 1.So, total 1s are 1.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

方法1：

将i从1迭代到n。
将i转换为字符串，并在每个整数字符串中计算“1”。
将每个字符串中的计数“1”添加到总和中。

下面是上述方法的代码。

C++

                         // c++ code to count the frequency of 1                       
                         // in numbers less than or equal to                       
                         // the given number.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                         int                                     countDigitOne(                                     int                                     n)                       
                         {                       
                                                 int                                     countr = 0;                       
                                                 for                                     (                                     int                                     i = 1; i <= n; i++) {                       
                                                 string str = to_string(i);                       
                                                 countr += count(str.begin(), str.end(),                                     '1'                                     );                       
                                                 }                       
                                                 return                                     countr;                       
                         }                       
           
                         // driver function                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 13;                       
                                                 cout << countDigitOne(n) << endl;                       
                                                 n = 131;                       
                                                 cout << countDigitOne(n) << endl;                       
                                                 n = 159;                       
                                                 cout << countDigitOne(n) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java code to count the frequency of 1                       
                         // in numbers less than or equal to                       
                         // the given number.                       
                         class                                     GFG                       
                         {                       
                         static                                     int                                     countDigitOne(                                     int                                     n)                       
                         {                       
                                                 int                                     countr =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= n; i++)                       
                                                 {                       
                                                 String str = String.valueOf(i);                       
                                                 countr += str.split(                                     "1"                                     , -                                     1                                     ) . length -                                     1                                     ;                       
                                                 }                       
                                                 return                                     countr;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     n =                                     13                                     ;                       
                                                 System.out.println(countDigitOne(n));                       
                                                 n =                                     131                                     ;                       
                                                 System.out.println(countDigitOne(n));                       
                                                 n =                                     159                                     ;                       
                                                 System.out.println(countDigitOne(n));                       
                         }                       
                         }                       
           
                         // This code is contributed by mits                       

Python3

                         # Python3 code to count the frequency                       
                         # of 1 in numbers less than or equal                       
                         # to the given number.                       
           
                         def                                     countDigitOne(n):                       
                                                 countr                                     =                                     0                                     ;                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ):                       
                                                 str1                                     =                                     str                                     (i);                       
                                                 countr                                     +                                     =                                     str1.count(                                     "1"                                     );                       
           
                                                 return                                     countr;                       
           
                         # Driver Code                       
                         n                                     =                                     13                                     ;                       
                         print                                     (countDigitOne(n));                       
           
                         n                                     =                                     131                                     ;                       
                         print                                     (countDigitOne(n));                       
           
                         n                                     =                                     159                                     ;                       
                         print                                     (countDigitOne(n));                       
           
                         # This code is contributed by mits                       

C#

                         // C# code to count the frequency of 1                       
                         // in numbers less than or equal to                       
                         // the given number.                       
                         using                                     System;                       
                         class                                     GFG                       
                         {                       
                         static                                     int                                     countDigitOne(                                     int                                     n)                       
                         {                       
                                                 int                                     countr = 0;                       
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 {                       
                                                 string                                     str = i.ToString();                       
                                                 countr += str.Split(                                     "1"                                     ) . Length - 1;                       
                                                 }                       
                                                 return                                     countr;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main()                       
                         {                       
                                                 int                                     n = 13;                       
                                                 Console.WriteLine(countDigitOne(n));                       
                                                 n = 131;                       
                                                 Console.WriteLine(countDigitOne(n));                       
                                                 n = 159;                       
                                                 Console.WriteLine(countDigitOne(n));                       
                         }                       
                         }                       
           
                         // This code is contributed by mits                       

PHP

                         <?php                       
                         // PHP code to count the frequency of 1                       
                         // in numbers less than or equal to                       
                         // the given number.                       
           
                         function                                     countDigitOne(                                     $n                                     )                       
                         {                       
                                                 $countr                                     = 0;                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 $str                                     =                                     strval                                     (                                     $i                                     );                       
                                                 $countr                                     += substr_count(                                     $str                                     ,                                     '1'                                     );                       
                                                 }                       
                                                 return                                     $countr                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 13;                       
                         echo                                     countDigitOne(                                     $n                                     ) .                                     ""                                     ;                       
           
                         $n                                     = 131;                       
                         echo                                     countDigitOne(                                     $n                                     ) .                                     ""                                     ;                       
           
                         $n                                     = 159;                       
                         echo                                     countDigitOne(                                     $n                                     ) .                                     ""                                     ;                       
           
                         // This code is contributed by mits                       
                         ?>                       

Javascript

                         <script>                       
                                   
                                                 // Javascript code to count the frequency of 1                       
                                                 // in numbers less than or equal to                       
                                                 // the given number.                       
                                   
                                                 function                                     countDigitOne(n)                       
                                                 {                       
                                                 let countr = 0;                       
                                                 for                                     (let i = 1; i <= n; i++)                       
                                                 {                       
                                                 let str = i.toString();                       
                                                 countr += str.split(                                     "1"                                     ) . length - 1;                       
                                                 }                       
                                                 return                                     countr;                       
                                                 }                       
                                   
                                                 let n = 13;                       
                                                 document.write(countDigitOne(n) +                                     "</br>"                                     );                       
                                                 n = 131;                       
                                                 document.write(countDigitOne(n) +                                     "</br>"                                     );                       
                                                 n = 159;                       
                                                 document.write(countDigitOne(n) +                                     "</br>"                                     );                       
                                   
                         </script>                       

输出：

时间复杂性： O（nlog（n）） 方法2：

将countr初始化为0。
从1迭代到n，每次递增10。
在每个（i*10）间隔后，将（n/（i*10））*i加到countr。
将最小值（最大值（n模（i*10）–i+1,0），i）添加到countr。

下面是上述方法的代码。

C++

                         // c++ code to count the frequency of 1                       
                         // in numbers less than or equal to                       
                         // the given number.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to count the frequency of 1.                       
                         int                                     countDigitOne(                                     int                                     n)                       
                         {                       
                                                 int                                     countr = 0;                       
                                                 for                                     (                                     int                                     i = 1; i <= n; i *= 10) {                       
                                                 int                                     divider = i * 10;                       
                                                 countr += (n / divider) * i +                       
                                                 min(max(n % divider - i + 1, 0), i);                       
                                                 }                       
                                                 return                                     countr;                       
                         }                       
           
                         // driver function                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 13;                       
                                                 cout << countDigitOne(n) << endl;                       
                                                 n = 113;                       
                                                 cout << countDigitOne(n) << endl;                       
                                                 n = 205;                       
                                                 cout << countDigitOne(n) << endl;                       
                         }                       

JAVA

                         /// Java code to count the                       
                         // frequency of 1 in numbers                       
                         // less than or equal to                       
                         // the given number.                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // function to count                       
                         // the frequency of 1.                       
                         static                                     int                                     countDigitOne(                                     int                                     n)                       
                         {                       
                                                 int                                     countr =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     1                                     ;                       
                                                 i <= n; i *=                                     10                                     )                       
                                                 {                       
                                                 int                                     divider = i *                                     10                                     ;                       
                                                 countr += (n / divider) * i +                       
                                                 Math.min(Math.max(n %                       
                                                 divider - i +                       
                                                 1                                     ,                                     0                                     ), i);                       
                                                 }                       
                                                 return                                     countr;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 int                                     n =                                     13                                     ;                       
                                                 System.out.println(countDigitOne(n));                       
                                   
                                                 n =                                     113                                     ;                       
                                                 System.out.println(countDigitOne(n));                       
                                   
                                                 n =                                     205                                     ;                       
                                                 System.out.println(countDigitOne(n));                       
                         }                       
                         }                       
           
                         // This code is contributed by akt_mit                       

Python3

                         # Python3 code to count the                       
                         # frequency of 1 in numbers                       
                         # less than or equal to                       
                         # the given number.                       
           
                         # function to count the                       
                         # frequency of 1.                       
                         def                                     countDigitOne(n):                       
                                                 countr                                     =                                     0                                     ;                       
                                                 i                                     =                                     1                                     ;                       
                                                 while                                     (i <                                     =                                     n):                       
                                                 divider                                     =                                     i                                     *                                     10                                     ;                       
                                                 countr                                     +                                     =                                     (                                     int                                     (n                                     /                                     divider)                                     *                                     i                                     +                       
                                                 min                                     (                                     max                                     (n                                     %                                     divider                                     -                                     i                                     +                       
                                                 1                                     ,                                     0                                     ), i));                       
                                                 i                                     *                                     =                                     10                                     ;                       
                                   
                                                 return                                     countr;                       
           
                         # Driver Code                       
                         n                                     =                                     13                                     ;                       
                         print                                     (countDigitOne(n));                       
                         n                                     =                                     113                                     ;                       
                         print                                     (countDigitOne(n));                       
                         n                                     =                                     205                                     ;                       
                         print                                     (countDigitOne(n));                       
           
                         # This code is contributed by mits                       

C#

                         // C# code to count the                       
                         // frequency of 1 in numbers                       
                         // less than or equal to                       
                         // the given number.                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                   
                         // function to count                       
                         // the frequency of 1.                       
                         static                                     int                                     countDigitOne(                                     int                                     n)                       
                         {                       
                                                 int                                     countr = 0;                       
                                                 for                                     (                                     int                                     i = 1;                       
                                                 i <= n; i *= 10)                       
                                                 {                       
                                                 int                                     divider = i * 10;                       
                                                 countr += (n / divider) * i +                       
                                                 Math.Min(Math.Max(n % divider -                       
                                                 i + 1, 0), i);                       
                                                 }                       
                                                 return                                     countr;                       
                         }                       
           
                         // Driver Code                       
                         public                                     static                                     void                                     Main()                       
                         {                       
                                                 int                                     n = 13;                       
                                                 Console.WriteLine(countDigitOne(n));                       
                                   
                                                 n = 113;                       
                                                 Console.WriteLine(countDigitOne(n));                       
                                   
                                                 n = 205;                       
                                                 Console.WriteLine(countDigitOne(n));                       
                         }                       
                         }                       
           
                         // This code is contributed by mits                       

PHP

                         <?php                       
                         // PHP code to count the                       
                         // frequency of 1 in numbers                       
                         // less than or equal to                       
                         // the given number.                       
           
                         // function to count the                       
                         // frequency of 1.                       
                         function                                     countDigitOne(                                     $n                                     )                       
                         {                       
                                                 $countr                                     = 0;                       
                                                 for                                     (                                     $i                                     = 1;                                     $i                                     <=                                     $n                                     ;                                     $i                                     *= 10)                       
                                                 {                       
                                                 $divider                                     =                                     $i                                     * 10;                       
                                                 $countr                                     += (int)(                                     $n                                     /                                     $divider                                     ) *                                     $i                                     +                       
                                                 min(max(                                     $n                                     %                                     $divider                                     -                       
                                                 $i                                     + 1, 0),                                     $i                                     );                       
                                                 }                       
                                   
                                                 return                                     $countr                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 13;                       
                         echo                                     countDigitOne(                                     $n                                     ),                                     ""                                     ;                       
                         $n                                     = 113;                       
                         echo                                     countDigitOne(                                     $n                                     ),                                     ""                                     ;                       
                         $n                                     = 205;                       
                         echo                                     countDigitOne(                                     $n                                     ),                                     ""                                     ;                       
           
                         // This code is contributed by ajit                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript code to count the frequency of 1                       
                         // in numbers less than or equal to                       
                         // the given number.                       
           
                         // function to count the frequency of 1.                       
                         function                                     countDigitOne(n)                       
                         {                       
                                                 var                                     countr = 0;                       
                                                 for                                     (                                     var                                     i = 1; i <= n; i *= 10) {                       
                                                 var                                     divider = i * 10;                       
                                                 countr += parseInt(n / divider) * i +                       
                                                 Math.min(Math.max(n % divider - i + 1, 0), i);                       
                                                 }                       
                                                 return                                     countr;                       
                         }                       
           
                         // driver function                       
                         var                                     n = 13;                       
                         document.write(countDigitOne(n)+                                     "<br>"                                     );                       
                         n = 113;                       
                         document.write(countDigitOne(n)+                                     "<br>"                                     );                       
                         n = 205;                       
                         document.write(countDigitOne(n)+                                     "<br>"                                     );                       
           
           
                         </script>                       

输出：

时间复杂性： O（对数（n））

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

THE END

技术文章