Given a positive integer n, find the count of each digit appearing in the integers from 1 to n | CODING INTERVIEW ARCHIVES

Given a positive integer n, find the count of each digit appearing in the integers from 1 to n | CODING INTERVIEW ARCHIVES

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

Read full article from Given a positive integer n, find the count of each digit appearing in the integers from 1 to n | CODING INTERVIEW ARCHIVES