Geek Answers Handbook

Sum of digits to a number that is indicated as input

If a number is entered as the input of the search for all digits of a number up to that number

For example, 11 is entered, then the answer is 1 + 2 .... + 9+ (1 + 0) + (1 + 1) The Brute-force method was to calculate the sum of the digits of all numbers that are less than the number. I implemented this method, wondering if there is another way to do this without actually calculating the sum of the digits of each number

0
source share
2 answers

You can do it faster (in O (log n) operations). Let be the S(n)sum of the digits of all numbers 0 <= k < n. Then

S(10*n) = 10*S(n) + 45*n

10*n k < n 10 , 0, 1, ..., 9. , 45 10 k.

,

S(n) = 10*S(n/10) + 45*(n/10) + (n%10)*DS(n/10) + (n%10)*((n%10)-1)/2

DS(k) - k. , - n - n%10, ..., n - n%10 + (n%10 + 1).

S(n) = 0 n <= 1.

, S(n+1).

+9

.

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

(10d - 1),

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

, . .

: sum (n)

1) n. "d".
328 d 2.

2) 1 10d - 1. w. 328 1 99, .

3) (msd) n. 328 msd 3.

4)

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))

aglorithm ++.

// 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;
}


Sum of digits in numbers from 1 to 328 is 3241
-1

More articles:


All Articles