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.
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.
Based on Divide and Conquer Coding Interviews: Questions, Analysis & Solutions
Also check http://stackoverflow.com/questions/20945790/count-the-number-of-ks-between-0-and-n
http://math.stackexchange.com/questions/47477/number-of-occurrences-of-the-digit-1-in-the-numbers-from-0-to-n
http://www.geeksforgeeks.org/number-of-occurrences-of-2-as-a-digit-in-numbers-from-0-to-n/
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.
Based on Divide and Conquer Coding Interviews: Questions, Analysis & Solutions
Also check http://stackoverflow.com/questions/20945790/count-the-number-of-ks-between-0-and-n
http://math.stackexchange.com/questions/47477/number-of-occurrences-of-the-digit-1-in-the-numbers-from-0-to-n
http://www.geeksforgeeks.org/number-of-occurrences-of-2-as-a-digit-in-numbers-from-0-to-n/
Count the number of 2s as digit in all numbers from 0 to n.
Input : 22
Output : 6
Explanation: Total 2s that appear as digit
from 0 to 22 are (2, 12, 20,
21, 22);
Improved Solution
The idea is to look at the problem digit by digit. Picture a sequence of numbers:
The idea is to look at the problem digit by digit. Picture a sequence of numbers:
0 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 ...... 110 111 112 113 114 115 116 117 118 119
We know that roughly one tenth of the time, the last digit will be a 2 since it happens once in any sequence of ten numbers. In fact, any digit is a 2 roughly one tenth of the time.
We say “roughly” because there are (very common) boundary conditions. For example, between 1 and 100, the 10’s digit is a 2 exactly 1/10th of the time. However, between 1 and 37, the 10’s digit is a 2 much more than 1/10th of the time.
We can work out what exactly the ratio is by looking at the three cases individually: digit 2.
Case digits < 2
Consider the value x = 61523 and digit at index d = 3 (here indexes are considered from right and rightmost index is 0). We observe that x[d] = 1. There are 2s at the 3rd digit in the ranges 2000 – 2999, 12000 – 12999, 22000 – 22999, 32000 32999, 42000 – 42999, and 52000 – 52999. So there are 6000 2’s total in the 3rd digit. This is the same amount as if we were just counting all the 2s in the 3rd digit between 1 and 60000.
Consider the value x = 61523 and digit at index d = 3 (here indexes are considered from right and rightmost index is 0). We observe that x[d] = 1. There are 2s at the 3rd digit in the ranges 2000 – 2999, 12000 – 12999, 22000 – 22999, 32000 32999, 42000 – 42999, and 52000 – 52999. So there are 6000 2’s total in the 3rd digit. This is the same amount as if we were just counting all the 2s in the 3rd digit between 1 and 60000.
In other words, we can round down to the nearest 10d+1, and then divide by 10, to compute the number of 2s in the d-th digit.
if x[d) < 2: count2sinRangeAtDigit(x, d) =
Compute y = round down to nearest 10d+1
return y/10
Case digit > 2
Now, let’s look at the case where d-th digit (from right) of x is greater than 2 (x[d] > 2). We can apply almost the exact same logic to see that there are the same number of 2s in the 3rd digit in the range 0 – 63525 as there as in the range 0 – 70000. So, rather than rounding down, we round up.
Now, let’s look at the case where d-th digit (from right) of x is greater than 2 (x[d] > 2). We can apply almost the exact same logic to see that there are the same number of 2s in the 3rd digit in the range 0 – 63525 as there as in the range 0 – 70000. So, rather than rounding down, we round up.
if x[d) > 2: count2sinRangeAtDigit(x, d) =
Compute y = round down to nearest 10d+1
return y / 10
Case digit = 2
The final case may be the trickiest, but it follows from the earlier logic. Consider x = 62523 and d = 3. We know that there are the same ranges of 2s from before (that is, the ranges 2000 – 2999, 12000 – 12999, … , 52000 – 52999). How many appear in the 3rd digit in the final, partial range from 62000 – 62523? Well, that should be pretty easy. It’s just 524 (62000, 62001, … , 62523).
The final case may be the trickiest, but it follows from the earlier logic. Consider x = 62523 and d = 3. We know that there are the same ranges of 2s from before (that is, the ranges 2000 – 2999, 12000 – 12999, … , 52000 – 52999). How many appear in the 3rd digit in the final, partial range from 62000 – 62523? Well, that should be pretty easy. It’s just 524 (62000, 62001, … , 62523).
if x[d] = 2: count2sinRangeAtDigit(x, d) = Compute y = round down to nearest 10d+1 Compute z = right side of x (i.e., x% 10d) return y/10 + z + 1
Now, all we need is to iterate through each digit in the number. Implementing this code is reasonably straightforward.
int count2sinRangeAtDigit(int number, int d){ int powerOf10 = (int)pow(10, d); int nextPowerOf10 = powerOf10 * 10; int right = number % powerOf10; int roundDown = number - number % nextPowerOf10; int roundup = roundDown + nextPowerOf10; int digit = (number / powerOf10) % 10; // if the digit in spot digit is if (digit < 2) return roundDown / 10; if (digit == 2) return roundDown / 10 + right+ 1; return roundup / 10;}/* Counts the number of '2' digits between 0 and n */int numberOf2sinRange(int number){ // Convert integer to String to find its length stringstream convert; convert << number; string s = convert.str(); int len = s.length(); /* Traverse every digit and count for every digit */ int count = 0; for (int digit= 0; digit < len; digit++) count += count2sinRangeAtDigit(number, digit); return count;}
A Simple Brute force solution is to iterate through all numbers from 0 to n. For every number being visited, count the number of 2’s in it. Finally return total count.
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