12241

Theory:

We know that,

• From 0-9, each digit occurs once
• From 0-99, each digit occurs 20 times (10x in position 1 and 10x in position 2)
• From 0-999, each digit occurs 300 times (100x in P1, 100x in P2, 100x in P3)

If the range is from 0 to a power of 10 then  occurrence of each digit is  N * 10^N-1, where N is the power of 10.

Length =7

0000001

0000002

……

0099999

…

9999900

…

1234567

If we consider it is a parallelogram of width = 7 and height = 1234567

Then total number of digits = 7 * 1234567 this include trailing and leading zeros(0).

The idea of counting all the digits is like taking the most significant digit and count all the digits from

0 to x*10^length-1 (x = most significant digit and length = total number of digits of the given number)

Let’s take 1234567 as the given number.

So total number of digits = total number of digits(from 0 to 1000000-1)

+ total number of digits (from 0 to 200000-1)+ previous most significant digit 1, 234567 times

+ total number of digits (from 0 to 30000-1)+ previous most significant digit 2, 34567 times

+ total number of digits (from 0 to 4000-1)+ previous most significant digit 3, 4567 times

+ total number of digits (from 0 to 500-1)+ previous most significant digit 4, 567 times

+ total number of digits (from 0 to 60-1)+ previous most significant digit 5,      67 times

+ total number of digits (from 0 to 7)+ previous most significant digit 6,

7 times

From total number of digits we found, contains total number of trailing zeros and digits from 1 to 9.

And total number of digits = 7 * 1234567 contains both leading and trailing zeros. So from here we can find the total number of leading zeros by subtracting the previous total number of zeros from 7 * 1234567.

 

 

Solution:

#include <iostream>

#define lld long long
using namespace std;

lld Digit[10],Digit2[10];

int getLenth(lld a)
{
	if(a<=9)
	return 0;

	int l=0;
	while(a)
	{
		a/=10;
		l++;
	}

	l--;
	//cout<<l<<"\n";
	return l;
}

int calDigit(lld n,lld digit[10])
{
    int pwr=-1,msd;
    lld org=n;
    lld mult=0;

    if(n==0)
    {
		return 0;
	}

    if(n<=9)
    {
        for(int i=1;i<=n;i++)
        digit[i]+=1;
        return 0;
    }
    while(n)
    {
       if(n<=9)
       msd=n;

       n/=10;
       mult*=10;
       pwr++;
       if(pwr==1)
       mult=1;
    }
    //like 0 to 99 2*1o^1 for each 0 to 9 and for upto 445 or 399 is msd*20=80 ,i.e n*10^(n-1),pwr=n and mult=10^(n-1),,msd = for each msd*(10^n)
    //cout<<(pwr)*mult<<"\n";
    //digit[0]+=(mult*msd);
    for(int i=0;i<10;i++)
        digit[i]+=(msd*pwr*mult);

    for(int i=0;i<msd;i++)
        digit[i]+=(mult*10);//mult=10^(power-1)


    digit[msd]+=(org+1-(msd*mult*10));
    calDigit(org%(mult*10),digit);
    return 0;
}

lld zerobalance(lld a,lld digit[10])
{
	lld lead_zero=0;
	lld nine=9;
	lld multi=1;
	int len = getLenth(a);

	lld total_digit = a*(len+1);// assume 445 : from 1 to 445 rectangle of 3 width 3*445 area ::including leading zeros
	lld total_non_zero = 0;

	//total digit from 1 to 9
	for(int i=1;i<=9;i++)
		total_non_zero+=digit[i];

	//total leading zero
	for(int i=0;i<=len;i++)
	{
	   nine=nine*multi;
	   lead_zero+=(nine*(len-i));
	   multi=10;
	}

	lld total_digit_zero = total_digit - total_non_zero - lead_zero;
	return total_digit_zero;
}

int main()
{
    lld n,m;

    for(int i=0;i<10;i++)
    {
       Digit[i]=0;
       Digit2[i]=0;
    }
    while(cin>>n)
    {
       cin>>m;
       if(n==0 && m==0)
       break;


       if(n)
       {
		   calDigit(n-1,Digit);
		   Digit[0] = zerobalance(n-1,Digit);
	   }
       else
		   Digit[0]=0;

       calDigit(m,Digit2);
	   Digit2[0] = zerobalance(m,Digit2);
       //cout<<Digit[0]<<" "<<Digit2[0]<<"\n";
       for(int i=0;i<10;i++)
       {
          cout<<Digit2[i]-Digit[i];
          cout<<(i==9 ? "\n" : " " );
          Digit2[i]=0;
          Digit[i]=0;
       }


    }

    return 0;
}