计算以4为数字的从1到n的数字-yiteyi-C++库

给定一个数字n，求出从1到n的所有数字中以4为数字的计数。 例如：

null

Input:   n = 5Output:  1Only 4 has '4' as digitInput:   n = 50Output:  14Input:   n = 328Output:  60

这个问题主要是上一篇文章的变体计算从1到n的所有数字的数字之和 .

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

天真的解决方案： 一个简单的解决方案是遍历从1到n的每个数字x，并检查x是否有4。为了检查x是否有，我们可以遍历x的所有数字。下面是上述想法的实现：

C++

                         // A Simple C++ program to compute sum of digits in numbers from 1 to n                       
                         #include<iostream>                       
                         using                                     namespace                                     std;                       
           
                         bool                                     has4(                                     int                                     x);                       
           
                         // Returns sum of all digits in numbers from 1 to n                       
                         int                                     countNumbersWith4(                                     int                                     n)                       
                         {                       
                                                 int                                     result = 0;                                     // initialize result                       
           
                                                 // One by one compute sum of digits in every number from                       
                                                 // 1 to n                       
                                                 for                                     (                                     int                                     x=1; x<=n; x++)                       
                                                 result += has4(x)? 1 : 0;                       
           
                                                 return                                     result;                       
                         }                       
           
                         // A utility function to compute sum of digits in a                       
                         // given number x                       
                         bool                                     has4(                                     int                                     x)                       
                         {                       
                                                 while                                     (x != 0)                       
                                                 {                       
                                                 if                                     (x%10 == 4)                       
                                                 return                                     true                                     ;                       
                                                 x   = x /10;                       
                                                 }                       
                                                 return                                     false                                     ;                       
                         }                       
           
                         // Driver Program                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 328;                       
                                                 cout <<                                     "Count of numbers from 1 to "                                     << n                       
                                                 <<                                     " that have 4 as a a digit is "                       
                                                 << countNumbersWith4(n) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to compute sum of                       
                         // digits in numbers from 1 to n                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
                                   
                                                 // Returns sum of all digits                       
                                                 // in numbers from 1 to n                       
                                                 static                                     int                                     countNumbersWith4(                                     int                                     n)                       
                                                 {                       
                                                 // initialize result                       
                                                 int                                     result =                                     0                                     ;                       
                                   
                                                 // One by one compute sum of digits                       
                                                 // in every number from 1 to n                       
                                                 for                                     (                                     int                                     x=                                     1                                     ; x<=n; x++)                       
                                                 result += has4(x)?                                     1                                     :                                     0                                     ;                       
                                   
                                                 return                                     result;                       
                                                 }                       
                                   
                                                 // A utility function to compute sum                       
                                                 // of digits in a given number x                       
                                                 static                                     boolean                                     has4(                                     int                                     x)                       
                                                 {                       
                                                 while                                     (x !=                                     0                                     )                       
                                                 {                       
                                                 if                                     (x%                                     10                                     ==                                     4                                     )                       
                                                 return                                     true                                     ;                       
                                                 x   = x /                                     10                                     ;                       
                                                 }                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                   
                                                 // Driver Program                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 int                                     n =                                     328                                     ;                       
                                                 System.out.println(                                     "Count of numbers from 1 to "                       
                                                 +                                     " that have 4 as a a digit is "                       
                                                 + countNumbersWith4(n)) ;                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Nikita Tiwari.                       

Python3

                         # A Simple Python 3 program to compute                       
                         # sum of digits in numbers from 1 to n                       
           
                         # Returns sum of all digits in numbers from 1 to n                       
                         def                                     countNumbersWith4(n) :                       
                                                 result                                     =                                     0                                     # initialize result                       
           
                                                 # One by one compute sum of digits                       
                                                 # in every number from 1 to n                       
                                                 for                                     x                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ) :                       
                                                 if                                     (has4(x)                                     =                                     =                                     True                                     ) :                       
                                                 result                                     =                                     result                                     +                                     1                       
           
                                                 return                                     result                       
           
                         # A utility function to compute sum                       
                         # of digits in a given number x                       
                         def                                     has4(x) :                       
                                                 while                                     (x !                                     =                                     0                                     ) :                       
                                                 if                                     (x                                     %                                     10                                     =                                     =                                     4                                     ) :                       
                                                 return                                     True                       
                                                 x                                     =                                     x                                     /                                     /                                     10                       
                                   
                                                 return                                     False                       
                                   
                         # Driver Program                       
                         n                                     =                                     328                       
                         print                                     (                                     "Count of numbers from 1 to "                                     , n,                       
                                                 " that have 4 as a a digit is "                                     ,                       
                                                 countNumbersWith4(n))                       
           
           
                         # This code is contributed by Nikita Tiwari.                       

C#

                         // C# program to compute sum of                       
                         // digits in numbers from 1 to n                       
                         using                                     System;                       
           
                         public                                     class                                     GFG                       
                         {                       
                                   
                                                 // Returns sum of all digits                       
                                                 // in numbers from 1 to n                       
                                                 static                                     int                                     countNumbersWith4(                                     int                                     n)                       
                                                 {                       
                                   
                                                 // initialize result                       
                                                 int                                     result = 0;                       
                                   
                                                 // One by one compute sum of digits                       
                                                 // in every number from 1 to n                       
                                                 for                                     (                                     int                                     x = 1; x <= n; x++)                       
                                                 result += has4(x) ? 1 : 0;                       
                                   
                                                 return                                     result;                       
                                                 }                       
                                   
                                                 // A utility function to compute sum                       
                                                 // of digits in a given number x                       
                                                 static                                     bool                                     has4(                                     int                                     x)                       
                                                 {                       
                                                 while                                     (x != 0)                       
                                                 {                       
                                                 if                                     (x % 10 == 4)                       
                                                 return                                     true                                     ;                       
                                                 x = x / 10;                       
                                                 }                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                   
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     n = 328;                       
                                                 Console.WriteLine(                                     "Count of numbers from 1 to "                       
                                                 +                                     " that have 4 as a a digit is "                       
                                                 + countNumbersWith4(n)) ;                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Sam007                       

PHP

                         <?php                       
                         // PHP program to compute sum of                       
                         // digits in numbers from 1 to n                       
           
                         // Returns sum of all digits                       
                         // in numbers from 1 to n                       
                         function                                     countNumbersWith4(                                     $n                                     )                       
                         {                       
                                                 $result                                     = 0;                                     // initialize result                       
           
                                                 // One by one compute sum of                       
                                                 // digits in every number from 1 to n                       
                                                 for                                     (                                     $x                                     = 1;                                     $x                                     <=                                     $n                                     ;                                     $x                                     ++)                       
                                                 $result                                     += has4(                                     $x                                     ) ? 1 : 0;                       
           
                                                 return                                     $result                                     ;                       
                         }                       
           
                         // A utility function to compute                       
                         // sum of digits in a given number x                       
                         function                                     has4(                                     $x                                     )                       
                         {                       
                                                 while                                     (                                     $x                                     != 0)                       
                                                 {                       
                                                 if                                     (                                     $x                                     % 10 == 4)                       
                                                 return                                     true;                       
                                                 $x                                     =                                     intval                                     (                                     $x                                     / 10);                       
                                                 }                       
                                                 return                                     false;                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 328;                       
                         echo                                     "Count of numbers from 1 to "                                     .                                     $n                                     .                       
                                                 " that have 4 as a a digit is "                                     .                       
                                                 countNumbersWith4(                                     $n                                     );                       
                                   
                         // This code is contributed by Sam007                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to compute sum of                       
                         // digits in numbers from 1 to n                       
           
                         // Returns sum of all digits                       
                         // in numbers from 1 to n                       
                         function                                     countNumbersWith4(n)                       
                         {                       
                                   
                                                 // Initialize result                       
                                                 let result = 0;                       
                                   
                                                 // One by one compute sum of digits                       
                                                 // in every number from 1 to n                       
                                                 for                                     (let x = 1; x <= n; x++)                       
                                                 result += has4(x) ? 1 : 0;                       
                                   
                                                 return                                     result;                       
                         }                       
           
                         // A utility function to compute sum                       
                         // of digits in a given number x                       
                         function                                     has4(x)                       
                         {                       
                                                 while                                     (x != 0)                       
                                                 {                       
                                                 if                                     (x % 10 == 4)                       
                                                 return                                     true                                     ;                       
                                   
                                                 x = Math.floor(x / 10);                       
                                                 }                       
                                                 return                                     false                                     ;                       
                         }                       
           
                         // Driver code                       
                         let n = 328;                       
                         document.write(                                     "Count of numbers from 1 to "                                     + n +                       
                                                 " that have 4 as a a digit is "                                     +                       
                                                 countNumbersWith4(n)) ;                       
           
                         // This code is contributed by avanitrachhadiya2155                       
                                   
                         </script>                       

输出：

Count of numbers from 1 to 328 that have 4 as a a digit is 60

使用DP的有效解决方案：

我们可以通过使用记忆技术的动态规划（DP）来提高上述方法的效率。我们可以在之前访问的整数中存储4的存在，这样每当我们需要检查这些整数时，就不需要通过再次检查每个数字来检查它是否包含4。要进行检查，我们只需从DP阵列进行检查。

下面是相同的代码：

C++

                         #include <iostream>                       
                         using                                     namespace                                     std;                       
           
                         bool                                     contains(                                     int                                     i);                       
           
                         int                                     countNumberswith4(                                     int                                     N)                       
                         {                       
                                                 int                                     count = 0;                       
           
                                                 bool                                     dp[N + 1]                       
                                                 = { 0 };                                     // boolean dp array to store whether                       
                                                 // the number contains digit '4' or not                       
           
                                                 for                                     (                                     int                                     i = 1; i <= N; i++) {                       
                                                 if                                     (dp[i]) {                                     // if dp[i] is true that means                       
                                                 // that number conatins digit '4'                       
                                                 count++;                       
                                                 continue                                     ;                                     // if it contains then no need to                       
                                                 // check again hence continue                       
                                                 }                       
           
                                                 if                                     (contains(i)) {                                     // check if i contains digit '4'                       
                                                 // or not                       
                                                 count++;                       
                                                 dp[i]                       
                                                 =                                     true                                     ;                                     // if it contains then mark dp[i] as                       
                                                 // true so that it can used later                       
                                                 }                       
                                                 }                       
           
                                                 return                                     count;                       
                         }                       
           
                         bool                                     contains(                                     int                                     i)                                     // boolean function to check                       
                         {                                     // whether i contains digit '4' or not                       
                                                 while                                     (i > 0) {                       
                                                 if                                     (i % 10 == 4)                       
                                                 return                                     true                                     ;                       
           
                                                 i /= 10;                       
                                                 }                       
                                                 return                                     false                                     ;                       
                         }                       
           
                         int                                     main()                       
                         {                       
           
                                                 int                                     n = 278;                       
                                                 cout <<                                     "Count of numbers from 1 to "                                     << n                       
                                                 <<                                     " that have 4 as a a digit is "                       
                                                 << countNumberswith4(n) << endl;                       
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by Anurag Mishra                       

JAVA

                         /*package whatever //do not write package name here */                       
           
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
           
                                                 static                                     int                                     countNumberswith4(                                     int                                     N)                       
                                                 {                       
                                                 int                                     count =                                     0                                     ;                       
           
                                                 boolean                                     dp[] =                                     new                                     boolean                       
                                                 [N +                                     1                                     ];                                     // boolean dp array to store whether                       
                                                 // the number contains digit '4' or not                       
           
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= N; i++) {                       
                                                 if                                     (dp[i]) {                                     // if dp[i] is true that means                       
                                                 // that number conatins digit '4'                       
                                                 count++;                       
                                                 continue                                     ;                                     // if it contains then no need to                       
                                                 // check again hence continue                       
                                                 }                       
           
                                                 if                                     (contains(i)) {                                     // check if i contains digit                       
                                                 // '4' or not                       
                                                 count++;                       
                                                 dp[i] =                                     true                                     ;                                     // if it contains then mark                       
                                                 // dp[i] as true so that it                       
                                                 // can used later                       
                                                 }                       
                                                 }                       
           
                                                 return                                     count;                       
                                                 }                       
           
                                                 static                                     boolean                       
                                                 contains(                                     int                                     i)                                     // boolean function to check                       
                                                 {                                     // whether i contains digit '4' or not                       
                                                 while                                     (i >                                     0                                     ) {                       
                                                 if                                     (i %                                     10                                     ==                                     4                                     )                       
                                                 return                                     true                                     ;                       
           
                                                 i /=                                     10                                     ;                       
                                                 }                       
                                                 return                                     false                                     ;                       
                                                 }                       
           
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     278                                     ;                       
                                                 System.out.println(                                     "Count of numbers from 1 to "                                     + n                       
                                                 +                                     " that have 4 as a a digit is "                       
                                                 + countNumberswith4(n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anurag Mishra                       

输出

Count of numbers from 1 to 278 that have 4 as a a digit is 55

另一个有效的解决方案：

上述第一个解决方案是一个幼稚的解决方案。我们可以通过找到一种模式来更有效地实现这一点。让我们举几个例子。

Count of numbers from 0 to 9   = 1Count of numbers from 0 to 99  = 1*9 + 10 = 19Count of numbers from 0 to 999 = 19*9 + 100 = 271 In general, we can write    count(10^d) =   9 * count(10^{d - 1}) + 10^{d - 1}

在下面的实现中，上述公式使用动态规划因为有重叠的子问题。上述公式是这个想法的核心步骤之一。下面是完整的算法。

1) Find number of digits minus one in n. Let this value be 'd'.     For 328, d is 2.2) Compute some of digits in numbers from 1 to 10^d - 1.     Let this sum be w. For 328, we compute sum of digits from 1 to    99 using above formula.3) Find Most significant digit (msd) in n. For 328, msd is 3.4.a) If MSD is 4. For example if n = 428, then count of     numbers is sum of following.     1) Count of numbers from 1 to 399     2) Count of numbers from 400 to 428 which is 29.4.b) IF MSD > 4. For example if n is 728, then count of     numbers is sum of following.     1) Count of numbers from 1 to 399 and count of numbers        from 500 to 699, i.e., "a[2] * 6"     2) Count of numbers from 400 to 499, i.e. 100     3) Count of numbers from 700 to 728, recur for 284.c) IF MSD < 4. For example if n is 328, then count of     numbers is sum of following.     1) Count of numbers from 1 to 299 a     2) Count of numbers from 300 to 328, recur for 28

下面是上述算法的实现。

C++

                         // C++ program to count numbers having 4 as a digit                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to count numbers from 1 to n that have                       
                         // 4 as a digit                       
                         int                                     countNumbersWith4(                                     int                                     n)                       
                         {                       
                                                 // Base case                       
                                                 if                                     (n < 4)                       
                                                 return                                     0;                       
           
                                                 // d = number of digits minus one in n. For 328, d is 2                       
                                                 int                                     d =                                     log10                                     (n);                       
           
                                                 // computing count of numbers from 1 to 10^d-1,                       
                                                 // d=0 a[0] = 0;                       
                                                 // d=1 a[1] = count of numbers from 0 to 9 = 1                       
                                                 // d=2 a[2] = count of numbers from 0 to 99 = a[1]*9 + 10 = 19                       
                                                 // d=3 a[3] = count of numbers from 0 to 999 = a[2]*19 + 100 = 171                       
                                                 int                                     *a =                                     new                                     int                                     [d+1];                       
                                                 a[0] = 0, a[1] = 1;                       
                                                 for                                     (                                     int                                     i=2; i<=d; i++)                       
                                                 a[i] = a[i-1]*9 +                                     ceil                                     (                                     pow                                     (10,i-1));                       
           
                                                 // Computing 10^d                       
                                                 int                                     p =                                     ceil                                     (                                     pow                                     (10, d));                       
           
                                                 // Most significant digit (msd) of n,                       
                                                 // For 328, msd is 3 which can be obtained using 328/100                       
                                                 int                                     msd = n/p;                       
           
                                                 // If MSD is 4. For example if n = 428, then count of                       
                                                 // numbers is sum of following.                       
                                                 // 1) Count of numbers from 1 to 399                       
                                                 // 2) Count of numbers from 400 to 428 which is 29.                       
                                                 if                                     (msd == 4)                       
                                                 return                                     (msd)*a[d] + (n%p) + 1;                       
           
                                                 // IF MSD > 4. For example if n is 728, then count of                       
                                                 // numbers is sum of following.                       
                                                 // 1) Count of numbers from 1 to 399 and count of numbers                       
                                                 //    from 500 to 699, i.e., "a[2] * 6"                       
                                                 // 2) Count of numbers from 400 to 499, i.e. 100                       
                                                 // 3) Count of numbers from 700 to 728, recur for 28                       
                                                 if                                     (msd > 4)                       
                                                 return                                     (msd-1)*a[d] + p + countNumbersWith4(n%p);                       
           
                                                 // IF MSD < 4. For example if n is 328, then count of                       
                                                 // numbers is sum of following.                       
                                                 // 1) Count of numbers from 1 to 299 a                       
                                                 // 2) Count of numbers from 300 to 328, recur for 28                       
                                                 return                                     (msd)*a[d] + countNumbersWith4(n%p);                       
                         }                       
           
                         // Driver Program                       
                         int                                     main()                       
                         {                       
                                                 int                                     n = 328;                       
                                                 cout <<                                     "Count of numbers from 1 to "                                     << n                       
                                                 <<                                     " that have 4 as a a digit is "                       
                                                 << countNumbersWith4(n) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count numbers having 4 as a digit                       
                         class                                     GFG                       
                         {                       
                                   
                         // Function to count numbers from                       
                         // 1 to n that have 4 as a digit                       
                         static                                     int                                     countNumbersWith4(                                     int                                     n)                       
                         {                       
                                                 // Base case                       
                                                 if                                     (n <                                     4                                     )                       
                                                 return                                     0                                     ;                       
                                   
                                                 // d = number of digits minus                       
                                                 // one in n. For 328, d is 2                       
                                                 int                                     d = (                                     int                                     )Math.log10(n);                       
           
                                                 // computing count of numbers from 1 to 10^d-1,                       
                                                 // d=0 a[0] = 0;                       
                                                 // d=1 a[1] = count of numbers from                       
                                                 // 0 to 9 = 1                       
                                                 // d=2 a[2] = count of numbers from                       
                                                 // 0 to 99 = a[1]*9 + 10 = 19                       
                                                 // d=3 a[3] = count of numbers from                       
                                                 // 0 to 999 = a[2]*19 + 100 = 171                       
                                                 int                                     [] a =                                     new                                     int                                     [d +                                     2                                     ];                       
                                                 a[                                     0                                     ] =                                     0                                     ;                       
                                                 a[                                     1                                     ] =                                     1                                     ;                       
           
                                                 for                                     (                                     int                                     i =                                     2                                     ; i <= d; i++)                       
                                                 a[i] = a[i -                                     1                                     ] *                                     9                                     + (                                     int                                     )Math.ceil(Math.pow(                                     10                                     , i -                                     1                                     ));                       
           
                                                 // Computing 10^d                       
                                                 int                                     p = (                                     int                                     )Math.ceil(Math.pow(                                     10                                     , d));                       
           
                                                 // Most significant digit (msd) of n,                       
                                                 // For 328, msd is 3 which can be obtained using 328/100                       
                                                 int                                     msd = n / p;                       
           
                                                 // If MSD is 4. For example if n = 428, then count of                       
                                                 // numbers is sum of following.                       
                                                 // 1) Count of numbers from 1 to 399                       
                                                 // 2) Count of numbers from 400 to 428 which is 29.                       
                                                 if                                     (msd ==                                     4                                     )                       
                                                 return                                     (msd) * a[d] + (n % p) +                                     1                                     ;                       
           
                                                 // IF MSD > 4. For example if n                       
                                                 // is 728, then count of numbers                       
                                                 // is sum of following.                       
                                                 // 1) Count of numbers from 1 to                       
                                                 // 399 and count of numbers from                       
                                                 // 500 to 699, i.e., "a[2] * 6"                       
                                                 // 2) Count of numbers from 400                       
                                                 // to 499, i.e. 100                       
                                                 // 3) Count of numbers from 700 to                       
                                                 // 728, recur for 28                       
                                                 if                                     (msd >                                     4                                     )                       
                                                 return                                     (msd -                                     1                                     ) * a[d] + p +                       
                                                 countNumbersWith4(n % p);                       
           
                                                 // IF MSD < 4. For example if n is 328, then count of                       
                                                 // numbers is sum of following.                       
                                                 // 1) Count of numbers from 1 to 299 a                       
                                                 // 2) Count of numbers from 300 to 328, recur for 28                       
                                                 return                                     (msd) * a[d] + countNumbersWith4(n % p);                       
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main (String[] args)                       
                         {                       
                                                 int                                     n =                                     328                                     ;                       
                                                 System.out.println(                                     "Count of numbers from 1 to "                                     + n +                       
                                                 " that have 4 as a digit is "                                     + countNumbersWith4(n));                       
                         }                       
                         }                       
           
                         // This code is contributed by chandan_jnu                       

Python3

                         # Python3 program to count numbers having 4 as a digit                       
                         import                                     math as mt                       
           
                         # Function to count numbers from 1 to n                       
                         # that have 4 as a digit                       
                         def                                     countNumbersWith4(n):                       
           
                                                 # Base case                       
                                                 if                                     (n <                                     4                                     ):                       
                                                 return                                     0                       
           
                                                 # d = number of digits minus one in n.                       
                                                 # For 328, d is 2                       
                                                 d                                     =                                     int                                     (mt.log10(n))                       
           
                                                 # computing count of numbers from 1 to 10^d-1,                       
                                                 # d=0 a[0] = 0                       
                                                 # d=1 a[1] = count of numbers from 0 to 9 = 1                       
                                                 # d=2 a[2] = count of numbers from                       
                                                 #            0 to 99 = a[1]*9 + 10 = 19                       
                                                 # d=3 a[3] = count of numbers from                       
                                                 #            0 to 999 = a[2]*19 + 100 = 171                       
                                                 a                                     =                                     [                                     1                                     for                                     i                                     in                                     range                                     (d                                     +                                     1                                     )]                       
                                                 a[                                     0                                     ]                                     =                                     0                       
                                                 if                                     len                                     (a) >                                     1                                     :                       
                                                 a[                                     1                                     ]                                     =                                     1                       
                                                 for                                     i                                     in                                     range                                     (                                     2                                     , d                                     +                                     1                                     ):                       
                                                 a[i]                                     =                                     a[i                                     -                                     1                                     ]                                     *                                     9                                     +                                     mt.ceil(                                     pow                                     (                                     10                                     , i                                     -                                     1                                     ))                       
           
                                                 # Computing 10^d                       
                                                 p                                     =                                     mt.ceil(                                     pow                                     (                                     10                                     , d))                       
           
                                                 # Most significant digit (msd) of n,                       
                                                 # For 328, msd is 3 which can be                       
                                                 # obtained using 328/100                       
                                                 msd                                     =                                     n                                     /                                     /                                     p                       
           
                                                 # If MSD is 4. For example if n = 428,                       
                                                 # then count of numbers is sum of following.                       
                                                 # 1) Count of numbers from 1 to 399                       
                                                 # 2) Count of numbers from 400 to 428 which is 29.                       
                                                 if                                     (msd                                     =                                     =                                     4                                     ):                       
                                                 return                                     (msd)                                     *                                     a[d]                                     +                                     (n                                     %                                     p)                                     +                                     1                       
           
                                                 # IF MSD > 4. For example if n is 728,                       
                                                 # then count of numbers is sum of following.                       
                                                 # 1) Count of numbers from 1 to 399 and count                       
                                                 #  of numbers from 500 to 699, i.e., "a[2] * 6"                       
                                                 # 2) Count of numbers from 400 to 499, i.e. 100                       
                                                 # 3) Count of numbers from 700 to 728, recur for 28                       
                                                 if                                     (msd >                                     4                                     ):                       
                                                 return                                     ((msd                                     -                                     1                                     )                                     *                                     a[d]                                     +                                     p                                     +                       
                                                 countNumbersWith4(n                                     %                                     p))                       
           
                                                 # IF MSD < 4. For example if n is 328,                       
                                                 # then count of numbers is sum of following.                       
                                                 # 1) Count of numbers from 1 to 299 a                       
                                                 # 2) Count of numbers from 300 to 328, recur for 28                       
                                                 return                                     (msd)                                     *                                     a[d]                                     +                                     countNumbersWith4(n                                     %                                     p)                       
           
                         # Driver Code                       
                         n                                     =                                     328                       
                         print                                     (                                     "Count of numbers from 1 to"                                     , n,                       
                                                 "that have 4 as a digit is"                                     , countNumbersWith4(n))                       
                                   
                         # This code is contributed by mohit kumar 29                       

C#

                         // C# program to count numbers having 4 as a digit                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                         // Function to count numbers from                       
                         //  1 to n that have 4 as a digit                       
                         static                                     int                                     countNumbersWith4(                                     int                                     n)                       
                         {                       
                                                 // Base case                       
                                                 if                                     (n < 4)                       
                                                 return                                     0;                       
                                   
                                                 // d = number of digits minus                       
                                                 // one in n. For 328, d is 2                       
                                                 int                                     d = (                                     int                                     )Math.Log10(n);                       
           
                                                 // computing count of numbers from 1 to 10^d-1,                       
                                                 // d=0 a[0] = 0;                       
                                                 // d=1 a[1] = count of numbers from                       
                                                 // 0 to 9 = 1                       
                                                 // d=2 a[2] = count of numbers from                       
                                                 // 0 to 99 = a[1]*9 + 10 = 19                       
                                                 // d=3 a[3] = count of numbers from                       
                                                 // 0 to 999 = a[2]*19 + 100 = 171                       
                                                 int                                     [] a =                                     new                                     int                                     [d+2];                       
                                                 a[0] = 0;                       
                                                 a[1] = 1;                       
           
                                                 for                                     (                                     int                                     i = 2; i <= d; i++)                       
                                                 a[i] = a[i - 1] * 9 + (                                     int                                     )Math.Ceiling(Math.Pow(10, i - 1));                       
           
                                                 // Computing 10^d                       
                                                 int                                     p = (                                     int                                     )Math.Ceiling(Math.Pow(10, d));                       
           
                                                 // Most significant digit (msd) of n,                       
                                                 // For 328, msd is 3 which can be obtained using 328/100                       
                                                 int                                     msd = n / p;                       
           
                                                 // If MSD is 4. For example if n = 428, then count of                       
                                                 // numbers is sum of following.                       
                                                 // 1) Count of numbers from 1 to 399                       
                                                 // 2) Count of numbers from 400 to 428 which is 29.                       
                                                 if                                     (msd == 4)                       
                                                 return                                     (msd) * a[d] + (n % p) + 1;                       
           
                                                 // IF MSD > 4. For example if n is 728, then count of                       
                                                 // numbers is sum of following.                       
                                                 // 1) Count of numbers from 1 to 399 and count of numbers                       
                                                 // from 500 to 699, i.e., "a[2] * 6"                       
                                                 // 2) Count of numbers from 400 to 499, i.e. 100                       
                                                 // 3) Count of numbers from 700 to 728, recur for 28                       
                                                 if                                     (msd > 4)                       
                                                 return                                     (msd - 1) * a[d] + p + countNumbersWith4(n % p);                       
           
                                                 // IF MSD < 4. For example if n is 328, then count of                       
                                                 // numbers is sum of following.                       
                                                 // 1) Count of numbers from 1 to 299 a                       
                                                 // 2) Count of numbers from 300 to 328, recur for 28                       
                                                 return                                     (msd) * a[d] + countNumbersWith4(n % p);                       
                         }                       
           
                         // Driver code                       
                         static                                     void                                     Main()                       
                         {                       
                                                 int                                     n = 328;                       
                                                 Console.WriteLine(                                     "Count of numbers from 1 to "                                     + n +                       
                                                 " that have 4 as a digit is "                                     + countNumbersWith4(n));                       
                         }                       
                         }                       
           
                         // This code is contributed by chandan_jnu                       

PHP

                         <?php                       
                         // PHP program to count numbers having                       
                         // 4 as a digit                       
           
                         // Function to count numbers from 1 to n                       
                         // that have 4 as a digit                       
                         function                                     countNumbersWith4(                                     $n                                     )                       
                         {                       
                                                 // Base case                       
                                                 if                                     (                                     $n                                     < 4)                       
                                                 return                                     0;                       
                                   
                                                 // d = number of digits minus one in n.                       
                                                 // For 328, d is 2                       
                                                 $d                                     = (int)log10(                                     $n                                     );                       
                                   
                                                 // computing count of numbers from 1 to 10^d-1,                       
                                                 // d=0 a[0] = 0;                       
                                                 // d=1 a[1] = count of numbers from 0 to 9 is 1                       
                                                 // d=2 a[2] = count of numbers from 0 to 99 is                       
                                                 //                            a[1]*9 + 10 = 19                       
                                                 // d=3 a[3] = count of numbers from 0 to 999 is                       
                                                 //                          a[2]*19 + 100 = 171                       
                                                 $a                                     =                                     array_fill                                     (0,                                     $d                                     + 1, NULL);                       
                                                 $a                                     [0] = 0;                       
                                                 $a                                     [1] = 1;                       
                                                 for                                     (                                     $i                                     = 2;                                     $i                                     <=                                     $d                                     ;                                     $i                                     ++)                       
                                                 $a                                     [                                     $i                                     ] =                                     $a                                     [                                     $i                                     - 1] * 9 +                       
                                                 ceil                                     (pow(10,                                     $i                                     - 1));                       
                                   
                                                 // Computing 10^d                       
                                                 $p                                     =                                     ceil                                     (pow(10,                                     $d                                     ));                       
           
                                                 // Most significant digit (msd) of n,                       
                                                 // For 328, msd is 3 which can be                       
                                                 // obtained using 328/100                       
                                                 $msd                                     =                                     intval                                     (                                     $n                                     /                                     $p                                     );                       
                                   
                                                 // If MSD is 4. For example if n = 428,                       
                                                 // then count of numbers is sum of following.                       
                                                 // 1) Count of numbers from 1 to 399                       
                                                 // 2) Count of numbers from 400 to 428 which is 29.                       
                                                 if                                     (                                     $msd                                     == 4)                       
                                                 return                                     (                                     $msd                                     ) *                                     $a                                     [                                     $d                                     ] + (                                     $n                                     %                                     $p                                     ) + 1;                       
                                   
                                                 // IF MSD > 4. For example if n is 728,                       
                                                 // then count of numbers is sum of following.                       
                                                 // 1) Count of numbers from 1 to 399 and                       
                                                 // count of numbers from 500 to 699, i.e., "a[2] * 6"                       
                                                 // 2) Count of numbers from 400 to 499, i.e. 100                       
                                                 // 3) Count of numbers from 700 to 728, recur for 28                       
                                                 if                                     (                                     $msd                                     > 4)                       
                                                 return                                     (                                     $msd                                     - 1) *                                     $a                                     [                                     $d                                     ] +                                     $p                                     +                       
                                                 countNumbersWith4(                                     $n                                     %                                     $p                                     );                       
                                   
                                                 // IF MSD < 4. For example if n is 328, then                       
                                                 // count of numbers is sum of following.                       
                                                 // 1) Count of numbers from 1 to 299 a                       
                                                 // 2) Count of numbers from 300 to 328, recur for 28                       
                                                 return                                     (                                     $msd                                     ) *                                     $a                                     [                                     $d                                     ] +                       
                                                 countNumbersWith4(                                     $n                                     %                                     $p                                     );                       
                         }                       
           
                         // Driver Code                       
                         $n                                     = 328;                       
                         echo                                     "Count of numbers from 1 to "                                     .                                     $n                                     .                       
                                                 " that have 4 as a digit is "                                     .                       
                                                 countNumbersWith4(                                     $n                                     ) .                                     ""                                     ;                       
           
                         // This code is contributed by ita_c                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to count numbers having 4 as a digit                       
                                   
                                                 // Function to count numbers from                       
                                                 // 1 to n that have 4 as a digit                       
                                                 function                                     countNumbersWith4(n)                       
                                                 {                       
                                   
                                                 // Base case                       
                                                 if                                     (n < 4)                       
                                                 return                                     0;                       
                                   
                                                 // d = number of digits minus                       
                                                 // one in n. For 328, d is 2                       
                                                 let d = Math.floor(Math.log10(n));                       
                                   
                                                 // computing count of numbers from 1 to 10^d-1,                       
                                                 // d=0 a[0] = 0;                       
                                                 // d=1 a[1] = count of numbers from                       
                                                 // 0 to 9 = 1                       
                                                 // d=2 a[2] = count of numbers from                       
                                                 // 0 to 99 = a[1]*9 + 10 = 19                       
                                                 // d=3 a[3] = count of numbers from                       
                                                 // 0 to 999 = a[2]*19 + 100 = 171                       
                                                 let a =                                     new                                     Array(d + 2);                       
                                                 for                                     (let i=0;i<d+2;i++)                       
                                                 {                       
                                                 a[i]=0;                       
                                                 }                       
                                                 a[0] = 0;                       
                                                 a[1] = 1;                       
                                   
                                                 for                                     (let i = 2; i <= d; i++)                       
                                                 a[i] = a[i - 1] * 9 + Math.floor(Math.ceil(Math.pow(10, i - 1)));                       
                                   
                                                 // Computing 10^d                       
                                                 let p = Math.floor(Math.ceil(Math.pow(10, d)));                       
                                   
                                                 // Most significant digit (msd) of n,                       
                                                 // For 328, msd is 3 which can be obtained using 328/100                       
                                                 let msd = Math.floor(n / p);                       
                                   
                                                 // If MSD is 4. For example if n = 428, then count of                       
                                                 // numbers is sum of following.                       
                                                 // 1) Count of numbers from 1 to 399                       
                                                 // 2) Count of numbers from 400 to 428 which is 29.                       
                                                 if                                     (msd == 4)                       
                                                 return                                     (msd) * a[d] + (n % p) + 1;                       
                                   
                                                 // IF MSD > 4. For example if n                       
                                                 // is 728, then count of numbers                       
                                                 // is sum of following.                       
                                                 // 1) Count of numbers from 1 to                       
                                                 // 399 and count of numbers from                       
                                                 // 500 to 699, i.e., "a[2] * 6"                       
                                                 // 2) Count of numbers from 400                       
                                                 // to 499, i.e. 100                       
                                                 // 3) Count of numbers from 700 to                       
                                                 // 728, recur for 28                       
                                                 if                                     (msd > 4)                       
                                                 return                                     (msd - 1) * a[d] + p +                       
                                                 countNumbersWith4(n % p);                       
                                   
                                                 // IF MSD < 4. For example if n is 328, then count of                       
                                                 // numbers is sum of following.                       
                                                 // 1) Count of numbers from 1 to 299 a                       
                                                 // 2) Count of numbers from 300 to 328, recur for 28                       
                                                 return                                     (msd) * a[d] + countNumbersWith4(n % p);                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 let n = 328;                       
                                                 document.write(                                     "Count of numbers from 1 to "                                     + n +                       
                                                 " that have 4 as a digit is "                                     + countNumbersWith4(n));                       
                                   
                                                 //  This code is contributed by rag2127                       
                         </script>                       

输出：

Count of numbers from 1 to 328 that have 4 as a a digit is 60

本文由 希瓦姆 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论

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

THE END

技术文章