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 * 10N-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*10length-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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 |
#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; } |