算法题：如何计算从1到n的所有数字的数字总和？

2021年3月30日12:33:07 发表评论 862 次浏览

本文概述

给定数字n, 请找到从1到n的所有数字的数字总和。

例子：

Input: n = 5
Output: Sum of digits in numbers from 1 to 5 = 15

Input: n = 12
Output: Sum of digits in numbers from 1 to 12 = 51

Input: n = 328
Output: Sum of digits in numbers from 1 to 328 = 3241

天真的解决方案：

一个朴素的解决方案是遍历从1到n的每个数字x, 并遍历x的所有数字来计算x中的总和。以下是此想法的实现。

C ++

// A Simple C++ program to compute sum of digits in numbers from 1 to n
#include<bits/stdc++.h>
using namespace std;
 
int sumOfDigits( int );
 
// Returns sum of all digits in numbers from 1 to n
int sumOfDigitsFrom1ToN( 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 += sumOfDigits(x);
 
     return result;
}
 
// A utility function to compute sum of digits in a
// given number x
int sumOfDigits( int x)
{
     int sum = 0;
     while (x != 0)
     {
         sum += x %10;
         x   = x /10;
     }
     return sum;
}
 
// Driver Program
int main()
{
     int n = 328;
     cout << "Sum of digits in numbers from 1 to " << n << " is "
          << sumOfDigitsFrom1ToN(n);
     return 0;
}

Java

// A Simple 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 sumOfDigitsFrom1ToN( 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 += sumOfDigits(x);
      
         return result;
     }
      
     // A utility function to compute sum
     // of digits in a given number x
     static int sumOfDigits( int x)
     {
         int sum = 0 ;
         while (x != 0 )
         {
             sum += x % 10 ;
             x   = x / 10 ;
         }
         return sum;
     }
      
     // Driver Program
     public static void main(String args[])
     {
         int n = 328 ;
         System.out.println( "Sum of digits in numbers"
                           + " from 1 to " + n + " is "
                           + sumOfDigitsFrom1ToN(n));
     }
}
 
/*This code is contributed by Nikita Tiwari.*/

Python3

# A Simple Python program to compute sum
# of digits in numbers from 1 to n
 
# Returns sum of all digits in numbers
# from 1 to n
def sumOfDigitsFrom1ToN(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 ) :
         result = result + sumOfDigits(x)
  
     return result
 
# A utility function to compute sum of
# digits in a given number x
def sumOfDigits(x) :
     sum = 0
     while (x ! = 0 ) :
         sum = sum + x % 10
         x   = x / / 10
     
     return sum
 
 
# Driver Program
n = 328
print ( "Sum of digits in numbers from 1 to" , n, "is" , sumOfDigitsFrom1ToN(n))
 
 
# This code is contributed by Nikita Tiwari.

C#

// A Simple 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 sumOfDigitsFrom1ToN( 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 += sumOfDigits(x);
     
         return result;
     }
     
     // A utility function to compute sum
     // of digits in a given number x
     static int sumOfDigits( int x)
     {
         int sum = 0;
         
         while (x != 0)
         {
             sum += x % 10;
             x = x / 10;
         }
         
         return sum;
     }
     
     // Driver Program
     public static void Main()
     {
         int n = 328;
         
         Console.WriteLine( "Sum of digits"
                + " in numbers from 1 to "
                              + n + " is "
                 + sumOfDigitsFrom1ToN(n));
     }
}
 
// This code is contributed by shiv_bhakt.

的PHP

<?php
 
// A Simple 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 sumOfDigitsFrom1ToN( $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 += sumOfDigits( $x );
 
     return $result ;
}
 
// A utility function to compute sum
// of digits in a given number x
function sumOfDigits( $x )
{
     $sum = 0;
     while ( $x != 0)
     {
         $sum += $x %10;
         $x = $x /10;
     }
     return $sum ;
}
 
// Driver Program
 
     $n = 328;
     echo "Sum of digits in numbers from"
                . " 1 to " . $n . " is "
                . sumOfDigitsFrom1ToN( $n );
     
// This code is contributed by ajit
?>

输出如下

Sum of digits in numbers from 1 to 328 is 3241

高效的解决方案：

以上是一个幼稚的解决方案。我们可以通过找到模式来更有效地做到这一点。

让我们举几个例子。

sum(9) = 1 + 2 + 3 + 4 ........... + 9
       = 9*10/2 
       = 45

sum(99)  = 45 + (10 + 45) + (20 + 45) + ..... (90 + 45)
         = 45*10 + (10 + 20 + 30 ... 90)
         = 45*10 + 10(1 + 2 + ... 9)
         = 45*10 + 45*10
         = sum(9)*10 + 45*10 

sum(999) = sum(99)*10 + 45*100

一般来说, 我们可以计算出sum(10d– 1)使用以下公式

sum(10d - 1) = sum(10d-1 - 1) * 10 + 45*(10d-1)

在下面的实现中, 上述公式使用

动态编程

因为存在重叠的子问题。

上式是这一想法的核心步骤。下面是完整的算法

算法：sum(n) 

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 10d - 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) Overall sum is sum of following terms

    a) Sum of digits in 1 to "msd * 10d - 1".  For 328, sum of 
       digits in numbers from 1 to 299.
        For 328, we compute 3*sum(99) + (1 + 2)*100.  Note that sum of
        sum(299) is sum(99) + sum of digits from 100 to 199 + sum of digits
        from 200 to 299.  
        Sum of 100 to 199 is sum(99) + 1*100 and sum of 299 is sum(99) + 2*100.
        In general, this sum can be computed as w*msd + (msd*(msd-1)/2)*10d

    b) Sum of digits in msd * 10d to n.  For 328, sum of digits in 
       300 to 328.
        For 328, this sum is computed as 3*29 + recursive call "sum(28)"
        In general, this sum can be computed as  msd * (n % (msd*10d) + 1) 
        + sum(n % (10d))

下面是上述算法的实现。

C ++

// C++ program to compute sum of digits in numbers from 1 to n
#include<bits/stdc++.h>
using namespace std;
 
// Function to computer sum of digits in numbers from 1 to n
// Comments use example of 328 to explain the code
int sumOfDigitsFrom1ToN( int n)
{
     // base case: if n<10 return sum of
     // first n natural numbers
     if (n<10)
       return n*(n+1)/2;
 
     // d = number of digits minus one in n. For 328, d is 2
     int d = log10 (n);
 
     // computing sum of digits from 1 to 10^d-1, // d=1 a[0]=0;
     // d=2 a[1]=sum of digit from 1 to 9 = 45
     // d=3 a[2]=sum of digit from 1 to 99 = a[1]*10 + 45*10^1 = 900
     // d=4 a[3]=sum of digit from 1 to 999 = a[2]*10 + 45*10^2 = 13500
     int *a = new int [d+1];
     a[0] = 0, a[1] = 45;
     for ( int i=2; i<=d; i++)
         a[i] = a[i-1]*10 + 45* 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;
 
     // EXPLANATION FOR FIRST and SECOND TERMS IN BELOW LINE OF CODE
     // First two terms compute sum of digits from 1 to 299
     // (sum of digits in range 1-99 stored in a[d]) +
     // (sum of digits in range 100-199, can be calculated as 1*100 + a[d]
     // (sum of digits in range 200-299, can be calculated as 2*100 + a[d]
     //  The above sum can be written as 3*a[d] + (1+2)*100
 
     // EXPLANATION FOR THIRD AND FOURTH TERMS IN BELOW LINE OF CODE
     // The last two terms compute sum of digits in number from 300 to 328
     // The third term adds 3*29 to sum as digit 3 occurs in all numbers
     //                from 300 to 328
     // The fourth term recursively calls for 28
     return msd*a[d] + (msd*(msd-1)/2)*p + 
            msd*(1+n%p) + sumOfDigitsFrom1ToN(n%p);
}
 
// Driver Program
int main()
{
     int n = 328;
     cout << "Sum of digits in numbers from 1 to " << n << " is "
          << sumOfDigitsFrom1ToN(n);
     return 0;
}

Java

// JAVA program to compute sum of digits
// in numbers from 1 to n
import java.io.*;
import java.math.*;
 
class GFG{
     
     // Function to computer sum of digits in
     // numbers from 1 to n. Comments use
     // example of 328 to explain the code
     static int sumOfDigitsFrom1ToN( int n)
     {
         // base case: if n<10 return sum of
         // first n natural numbers
         if (n < 10 )
           return (n * (n + 1 ) / 2 );
      
         // d = number of digits minus one in
         // n. For 328, d is 2
         int d = ( int )(Math.log10(n));
      
         // computing sum of digits from 1 to 10^d-1, // d=1 a[0]=0;
         // d=2 a[1]=sum of digit from 1 to 9 = 45
         // d=3 a[2]=sum of digit from 1 to 99 =
         // a[1]*10 + 45*10^1 = 900
         // d=4 a[3]=sum of digit from 1 to 999 =
         // a[2]*10 + 45*10^2 = 13500
         int a[] = new int [d+ 1 ];
         a[ 0 ] = 0 ; a[ 1 ] = 45 ;
         for ( int i = 2 ; i <= d; i++)
             a[i] = a[i- 1 ] * 10 + 45 *
                  ( 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;
      
         // EXPLANATION FOR FIRST and SECOND TERMS IN
         // BELOW LINE OF CODE
         // First two terms compute sum of digits from
         // 1 to 299
         // (sum of digits in range 1-99 stored in a[d]) +
         // (sum of digits in range 100-199, can be
         // calculated as 1*100 + a[d]
         // (sum of digits in range 200-299, can be
         // calculated as 2*100 + a[d]
         //  The above sum can be written as 3*a[d] +
         // (1+2)*100
      
         // EXPLANATION FOR THIRD AND FOURTH TERMS IN
         // BELOW LINE OF CODE
         // The last two terms compute sum of digits in
         // number from 300 to 328. The third term adds
         // 3*29 to sum as digit 3 occurs in all numbers
         // from 300 to 328. The fourth term recursively
         // calls for 28
         return (msd * a[d] + (msd * (msd - 1 ) / 2 ) * p + 
               msd * ( 1 + n % p) + sumOfDigitsFrom1ToN(n % p));
     }
      
     // Driver Program
     public static void main(String args[])
     {
         int n = 328 ;
         System.out.println( "Sum of digits in numbers " +
                           "from 1 to " +n + " is " +
                           sumOfDigitsFrom1ToN(n));
     }
}
 
/*This code is contributed by Nikita Tiwari.*/

Python3

# PYTHON 3 program to compute sum of digits
# in numbers from 1 to n
import math
 
# Function to computer sum of digits in
# numbers from 1 to n. Comments use example
# of 328 to explain the code
def sumOfDigitsFrom1ToN( n) :
   
     # base case: if n<10 return sum of
     # first n natural numbers
     if (n< 10 ) :
         return (n * (n + 1 ) / 2 )
  
     # d = number of digits minus one in n.
     # For 328, d is 2
     d = ( int )(math.log10(n))
  
     """computing sum of digits from 1 to 10^d-1, d=1 a[0]=0;
     d=2 a[1]=sum of digit from 1 to 9 = 45
     d=3 a[2]=sum of digit from 1 to 99 = a[1]*10
     + 45*10^1 = 900
     d=4 a[3]=sum of digit from 1 to 999 = a[2]*10
     + 45*10^2 = 13500"""
     a = [ 0 ] * (d + 1 )
     a[ 0 ] = 0
     a[ 1 ] = 45
     for i in range ( 2 , d + 1 ) :
         a[i] = a[i - 1 ] * 10 + 45 * ( int )(math.ceil(math. pow ( 10 , i - 1 )))
  
     # computing 10^d
     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
     msd = n / / p
  
     """EXPLANATION FOR FIRST and SECOND TERMS IN
     BELOW LINE OF CODE
     First two terms compute sum of digits from 1 to 299
     (sum of digits in range 1-99 stored in a[d]) +
     (sum of digits in range 100-199, can be calculated
     as 1*100 + a[d]. (sum of digits in range 200-299, can be calculated as 2*100 + a[d]
     The above sum can be written as 3*a[d] + (1+2)*100
  
     EXPLANATION FOR THIRD AND FOURTH TERMS IN BELOW
     LINE OF CODE
     The last two terms compute sum of digits in number
     from 300 to 328. The third term adds 3*29 to sum
     as digit 3 occurs in all numbers from 300 to 328.
     The fourth term recursively calls for 28"""
     return ( int )(msd * a[d] + (msd * (msd - 1 ) / / 2 ) * p + 
            msd * ( 1 + n % p) + sumOfDigitsFrom1ToN(n % p))
 
# Driver Program
n = 328
print ( "Sum of digits in numbers from 1 to" , n , "is" , sumOfDigitsFrom1ToN(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 {
     
     // Function to computer sum of digits in
     // numbers from 1 to n. Comments use
     // example of 328 to explain the code
     static int sumOfDigitsFrom1ToN( int n)
     {
         
         // base case: if n<10 return sum of
         // first n natural numbers
         if (n < 10)
             return (n * (n + 1) / 2);
     
         // d = number of digits minus one in
         // n. For 328, d is 2
         int d = ( int )(Math.Log(n) / Math.Log(10));
     
         // computing sum of digits from 1 to 10^d-1, // d=1 a[0]=0;
         // d=2 a[1]=sum of digit from 1 to 9 = 45
         // d=3 a[2]=sum of digit from 1 to 99 =
         // a[1]*10 + 45*10^1 = 900
         // d=4 a[3]=sum of digit from 1 to 999 =
         // a[2]*10 + 45*10^2 = 13500
         int [] a = new int [d+1];
         a[0] = 0; a[1] = 45;
         
         for ( int i = 2; i <= d; i++)
             a[i] = a[i-1] * 10 + 45 *
                 ( 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;
     
         // EXPLANATION FOR FIRST and SECOND TERMS IN
         // BELOW LINE OF CODE
         // First two terms compute sum of digits from
         // 1 to 299
         // (sum of digits in range 1-99 stored in a[d]) +
         // (sum of digits in range 100-199, can be
         // calculated as 1*100 + a[d]
         // (sum of digits in range 200-299, can be
         // calculated as 2*100 + a[d]
         // The above sum can be written as 3*a[d] +
         // (1+2)*100
     
         // EXPLANATION FOR THIRD AND FOURTH TERMS IN
         // BELOW LINE OF CODE
         // The last two terms compute sum of digits in
         // number from 300 to 328. The third term adds
         // 3*29 to sum as digit 3 occurs in all numbers
         // from 300 to 328. The fourth term recursively
         // calls for 28
         return (msd * a[d] + (msd * (msd - 1) / 2) * p +
             msd * (1 + n % p) + sumOfDigitsFrom1ToN(n % p));
     }
     
     // Driver Program
     public static void Main()
     {
         int n = 328;
         Console.WriteLine( "Sum of digits in numbers " +
                              "from 1 to " +n + " is " +
                                sumOfDigitsFrom1ToN(n));
     }
}
 
// This code is contributed by shiv_bhakt.

的PHP

<?php
// PHP program to compute sum of digits
// in numbers from 1 to n
 
// Function to computer sum of digits in
// numbers from 1 to n. Comments use
// example of 328 to explain the code
function sumOfDigitsFrom1ToN( $n )
{
     // base case: if n<10 return sum of
     // first n natural numbers
     if ( $n < 10)
     return ( $n * ( $n + 1) / 2);
 
     // d = number of digits minus one in
     // n. For 328, d is 2
     $d = (int)(log10( $n ));
 
     // computing sum of digits from 1
     // to 10^d-1, d=1 a[0]=0;
     // d=2 a[1]=sum of digit from 1 to 9 = 45
     // d=3 a[2]=sum of digit from 1 to 99 =
     // a[1]*10 + 45*10^1 = 900
     // d=4 a[3]=sum of digit from 1 to 999 =
     // a[2]*10 + 45*10^2 = 13500
     $a [ $d + 1] = array ();
     $a [0] = 0;
     $a [1] = 45;
     for ( $i = 2; $i <= $d ; $i ++)
         $a [ $i ] = $a [ $i - 1] * 10 + 45 *
                  (int)( ceil (pow(10, $i - 1)));
 
     // computing 10^d
     $p = (int)( ceil (pow(10, $d )));
 
     // Most significant digit (msd) of n, // For 328, msd is 3 which can be obtained
     // using 328/100
     $msd = (int)( $n / $p );
 
     // EXPLANATION FOR FIRST and SECOND
     // TERMS IN BELOW LINE OF CODE
     // First two terms compute sum of
     // digits from 1 to 299
     // (sum of digits in range 1-99 stored
     // in a[d]) + (sum of digits in range
     // 100-199, can be calculated as 1*100 + a[d]
     // (sum of digits in range 200-299, // can be calculated as 2*100 + a[d]
     // The above sum can be written as
     // 3*a[d] + (1+2)*100
 
     // EXPLANATION FOR THIRD AND FOURTH
     // TERMS IN BELOW LINE OF CODE
     // The last two terms compute sum of digits in
     // number from 300 to 328. The third term adds
     // 3*29 to sum as digit 3 occurs in all numbers
     // from 300 to 328. The fourth term recursively
     // calls for 28
     return ( $msd * $a [ $d ] + ( $msd * (int)( $msd - 1) / 2) * $p +
             $msd * (1 + $n % $p ) + sumOfDigitsFrom1ToN( $n % $p ));
}
 
// Driver Code
$n = 328;
echo ( "Sum of digits in numbers " ), "from 1 to " , $n , " is " , sumOfDigitsFrom1ToN( $n );
 
// This code is contributed by Sachin
?>

输出如下：

Sum of digits in numbers from 1 to 328 is 3241

高效的算法还有一个优势, 即使给了多个输入, 我们也只需计算一次数组" a []"。

改善：

上述实现需要O(d^2)时间，因为每次递归调用再次计算dp[]数组。第一次调用为O(d)，第二次调用为O(d-1)，第三次调用为O(d-2)，以此类推。我们不需要在每次递归调用中重新计算dp[]数组。下面是修改后的实现，它在O(d)时间内工作。其中d是输入数中的位数。

C ++

// C++ program to compute sum of digits
// in numbers from 1 to n
#include<bits/stdc++.h>
using namespace std;
 
int sumOfDigitsFrom1ToNUtil( int n, int a[])
{
     if (n < 10)
         return (n * (n + 1) / 2);
     
     int d = ( int )( log10 (n));
     int p = ( int )( ceil ( pow (10, d)));
     int msd = n / p;
     
     return (msd * a[d] + (msd * (msd - 1) / 2) * p +
             msd * (1 + n % p) +
             sumOfDigitsFrom1ToNUtil(n % p, a));
}
 
// Function to computer sum of digits in
// numbers from 1 to n
int sumOfDigitsFrom1ToN( int n)
{
     int d = ( int )( log10 (n));
     int a[d + 1];
     a[0] = 0; a[1] = 45;
     
     for ( int i = 2; i <= d; i++)
         a[i] = a[i - 1] * 10 + 45 *
                ( int )( ceil ( pow (10, i - 1)));
 
     return sumOfDigitsFrom1ToNUtil(n, a);
}
  
// Driver code
int main()
{
     int n = 328;
     
     cout << "Sum of digits in numbers from 1 to "
          << n << " is " << sumOfDigitsFrom1ToN(n);
}
 
// This code is contributed by ajaykr00kj

Java

// JAVA program to compute sum of digits
// in numbers from 1 to n
import java.io.*;
import java.math.*;
 
class GFG{
     
     // Function to computer sum of digits in
     // numbers from 1 to n
     static int sumOfDigitsFrom1ToN( int n)
     {
         int d = ( int )(Math.log10(n));
         int a[] = new int [d+ 1 ];
         a[ 0 ] = 0 ; a[ 1 ] = 45 ;
         for ( int i = 2 ; i <= d; i++)
             a[i] = a[i- 1 ] * 10 + 45 *
                 ( int )(Math.ceil(Math.pow( 10 , i- 1 )));
     
         return sumOfDigitsFrom1ToNUtil(n, a);
     }
    
     static int sumOfDigitsFrom1ToNUtil( int n, int a[])
     {
         if (n < 10 )
             return (n * (n + 1 ) / 2 );
       
         int d = ( int )(Math.log10(n));
         int p = ( int )(Math.ceil(Math.pow( 10 , d)));
         int msd = n / p;
         return (msd * a[d] + (msd * (msd - 1 ) / 2 ) * p +
             msd * ( 1 + n % p) + sumOfDigitsFrom1ToNUtil(n % p, a));
     }
     
     // Driver Program
     public static void main(String args[])
     {
         int n = 328 ;
         System.out.println( "Sum of digits in numbers " +
                         "from 1 to " +n + " is " +
                         sumOfDigitsFrom1ToN(n));
     }
}
 
/*This code is contributed by Narendra Jha.*/

Python3

# Python program to compute sum of digits
# in numbers from 1 to n
import math
 
# Function to computer sum of digits in
# numbers from 1 to n
def sumOfDigitsFrom1ToN(n):
     
     d = int (math.log(n, 10 ))
     a = [ 0 ] * (d + 1 )
     a[ 0 ] = 0
     a[ 1 ] = 45
     for i in range ( 2 , d + 1 ):
         a[i] = a[i - 1 ] * 10 + 45 * \
                 int (math.ceil( pow ( 10 , i - 1 )))
         
     return sumOfDigitsFrom1ToNUtil(n, a)
 
def sumOfDigitsFrom1ToNUtil(n, a):
     if (n < 10 ):
         return (n * (n + 1 )) / / 2
     
     d = int (math.log(n, 10 ))
     p = int (math.ceil( pow ( 10 , d)))
     msd = n / / p
     return (msd * a[d] + (msd * (msd - 1 ) / / 2 ) * p +
     msd * ( 1 + n % p) + sumOfDigitsFrom1ToNUtil(n % p, a))
 
# Driver code
n = 328
print ( "Sum of digits in numbers from 1 to" , n, "is" , sumOfDigitsFrom1ToN(n))
 
# This code is contributed by shubhamsingh10

C#

// C# program to compute sum of digits
// in numbers from 1 to n
using System;
 
class GFG
{
     
     // Function to computer sum of digits in
     // numbers from 1 to n
     static int sumOfDigitsFrom1ToN( int n)
     {
         int d = ( int )(Math.Log10(n));
         int []a = new int [d+1];
         a[0] = 0; a[1] = 45;
         for ( int i = 2; i <= d; i++)
             a[i] = a[i-1] * 10 + 45 *
                 ( int )(Math.Ceiling(Math.Pow(10, i-1)));
     
         return sumOfDigitsFrom1ToNUtil(n, a);
     }
     
     static int sumOfDigitsFrom1ToNUtil( int n, int []a)
     {
         if (n < 10)
             return (n * (n + 1) / 2);
         
         int d = ( int )(Math.Log10(n));
         int p = ( int )(Math.Ceiling(Math.Pow(10, d)));
         int msd = n / p;
         return (msd * a[d] + (msd * (msd - 1) / 2) * p +
             msd * (1 + n % p) + sumOfDigitsFrom1ToNUtil(n % p, a));
     }
     
     // Driver code
     public static void Main(String []args)
     {
         int n = 328;
         Console.WriteLine( "Sum of digits in numbers " +
                         "from 1 to " +n + " is " +
                         sumOfDigitsFrom1ToN(n));
     }
}
 
// This code contributed by Rajput-Ji

输出：

Sum of digits in numbers from 1 to 328 is 3241

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

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: