Translate

Friday, 30 January 2015

Formula for calculating the sum of Digits from 1 to n

HII GUYS>>>>>>>>

First of all i just explain u by one example.........
1.one important thing is the sum of 1+2+3+.........+9=45
2.now u have to find out that how many times this sum(45) will occur......
3.example::
      let u want to find out sum of digits of 1 to 52.
      then just notice how i m reaching to 92.
     i.e 1,2,3..........9
         11,12,13,...........19
         21,22,23,,,,,,,,,,,,,,,,29
         31,32,,,,,,,,,,,,,,,,,,,,,,39
         41,42,,,,,,,,,,,,,,,,,,,,,49
         10,20,30,40,50
         51,52
        
         just think how i m making sets....
        1. now observe how many sum(1+2+3+......+9=45)  occuring
         5 times sum(45) occuring
         
        2.10times 1,10 times 2,10 times 3,10 times 4
           so i can write this sum as (1+2+3+4) *10 times
                                                 formula for this=4*5*10/2
    
        3.for 50,51 ,52 i.e how many times 5 occuring...
           i.e 3 times i can write this as 5*(2+1) or 5*(52%10+1)
        
         4.now for 0+1+2=2*3/2

so finally formula for this is

int sumofDigit(int N)
{
if(N<10)
return N*(N+1)/2;
int n=N,i;
while(n/10!=0)
{
i++;
n/=10;
}
int p=pow(10,i);
return ((n*i*45*p/10)+(n*(n-1)*p/2)+n*(N%p+1)+sumofDigit(N%p));
}
                    
         
   PRACTICE PROBLEM::

  http://www.spoj.com/problems/CPCRC1C/
  http://www.spoj.com/problems/PR003004/      
         

No comments:

Working With Java Collections