Given a positive integer n, find the count of each digit appearing in the integers from 1 to n | CODING INTERVIEW ARCHIVES
Thus, for all 1 digit integers, each digit has a count of 1 (1*(10^0)), except '0', which has count of 0 (1*(10^0)-1), since 0 is not valid.
There are 100 possible 1 or 2 digit integers, thus total number of digits are 200(100*2). Each digit is equally likely.
Thus, for all 2 digit integers, each digit has a count of 20 (2*(10^1)), except '0', which has count of 9 (2*(10^1)-11), since 00,01,02,...09 are 1 digit numbers.
There are 1000 possible 1 or 2 or 3 digit integers, thus total number of digits are 3000(1000*3). Each digit is equally likely.
Thus, for all 3 digit integers, each digit has a count of 300 (3*(10^2)), except '0', which has count of 189 (3*(10^2)-111), since 000,001,...009,010,011,...099 are either 1 or 2 digit numbers and thus the count of zero needs to be subtracted.
And so on..
Now consider n to be a 'k' digit integer.
Let the first(Most Significant) digit be d. Thus, all the 'k-1' digit integers appear d times. Thus the count of each digit is increased by 'd' times the count of each digit in all of 'k-1' digit integers.
Count of digits from 1 to d-1 is further increased by 10^(k-1) as they appear at the beginning of each k-1 digit integer.
Count of digit d is further increased by n%(10^(k-1))+1, as it appears at the starting of all integers from 0 to n%(10^(k-1)).
Similarly, consider all the digits one by one till the Least Significant Digit.
Finally, those integers are reconsidered which have 1 or more zeroes at the beginning, and thus the count of 0 is reduced as explained above.
The problem is to find the count of each digit (0 to 9), which occur in integers starting from 1, upto a given integer n.
A brute force approach is to consider each and every digit in all the integers from 1 to n. This will have a complexity of O(n), which is not feasible if n is greater than 10^7.
The approach discussed here has a very less complexity than the brute approach. The complexity is O(number of digits in n)!
Approach:
There are 10 possible 1 digit integers, thus total number of digits are 10(10*1). Each digit is equally likely.
Thus, for all 1 digit integers, each digit has a count of 1 (1*(10^0)), except '0', which has count of 0 (1*(10^0)-1), since 0 is not valid.
There are 100 possible 1 or 2 digit integers, thus total number of digits are 200(100*2). Each digit is equally likely.
Thus, for all 2 digit integers, each digit has a count of 20 (2*(10^1)), except '0', which has count of 9 (2*(10^1)-11), since 00,01,02,...09 are 1 digit numbers.
There are 1000 possible 1 or 2 or 3 digit integers, thus total number of digits are 3000(1000*3). Each digit is equally likely.
Thus, for all 3 digit integers, each digit has a count of 300 (3*(10^2)), except '0', which has count of 189 (3*(10^2)-111), since 000,001,...009,010,011,...099 are either 1 or 2 digit numbers and thus the count of zero needs to be subtracted.
And so on..
Now consider n to be a 'k' digit integer.
Let the first(Most Significant) digit be d. Thus, all the 'k-1' digit integers appear d times. Thus the count of each digit is increased by 'd' times the count of each digit in all of 'k-1' digit integers.
Count of digits from 1 to d-1 is further increased by 10^(k-1) as they appear at the beginning of each k-1 digit integer.
Count of digit d is further increased by n%(10^(k-1))+1, as it appears at the starting of all integers from 0 to n%(10^(k-1)).
Similarly, consider all the digits one by one till the Least Significant Digit.
Finally, those integers are reconsidered which have 1 or more zeroes at the beginning, and thus the count of 0 is reduced as explained above.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
int* getDigitCount(int n){
int m=n,k=0,ones=0;
while(m){
ones=ones*10+1;
k++;
m=m/10;
}
int *d=malloc(sizeof(int)*10);
memset(d,0,10*sizeof(int));
int tens=ceil(pow(10,k-1));
int i,j;
while(tens){
int dig=(n/tens)%10;
int rest=n%tens;
k--;
for(i=0;i<10;i++){
d[i]=d[i]+((dig*(tens/10)*k));
}
for(i=0;i<dig;i++){
d[i]=d[i]+tens;
}
d[dig]+=(rest+1);
tens/=10;
}
d[0]=d[0]-ones;
return d;
}
int main(){
int n=9999;
int *dig,i;
dig=getDigitCount(n);
for(i=0;i<10;i++){
printf("%d\n",dig[i]);
}
return 0;
} 