How to count each digit in a range of integers?

Question

Imagine you sell those metallic digits used to number houses, locker doors, hotel rooms, etc. You need to find how many of each digit to ship when your customer needs to number doors/houses:

• 1 to 100
• 51 to 300
• 1 to 2,000 with zeros to the left

The obvious solution is to do a loop from the first to the last number, convert the counter to a string with or without zeros to the left, extract each digit and use it as an index to increment an array of 10 integers.

I wonder if there is a better way to solve this, without having to loop through the entire integers range.

Solutions in any language or pseudocode are welcome.

---

Edit:

Answers review
John at CashCommons and Wayne Conrad comment that my current approach is good and fast enough. Let me use a silly analogy: If you were given the task of counting the squares in a chess board in less than 1 minute, you could finish the task by counting the squares one by one, but a better solution is to count the sides and do a multiplication, because you later may be asked to count the tiles in a building.
Alex Reisner points to a very interesting mathematical law that, unfortunately, doesn’t seem to be relevant to this problem.
Andres suggests the same algorithm I’m using, but extracting digits with %10 operations instead of substrings.
John at CashCommons and phord propose pre-calculating the digits required and storing them in a lookup table or, for raw speed, an array. This could be a good solution if we had an absolute, unmovable, set in stone, maximum integer value. I’ve never seen one of those.
High-Performance Mark and strainer computed the needed digits for various ranges. The result for one millon seems to indicate there is a proportion, but the results for other number show different proportions.
strainer found some formulas that may be used to count digit for number which are a power of ten. Robert Harvey had a very interesting experience posting the question at MathOverflow. One of the math guys wrote a solution using mathematical notation.
Aaronaught developed and tested a solution using mathematics. After posting it he reviewed the formulas originated from Math Overflow and found a flaw in it (point to Stackoverflow :).
noahlavine developed an algorithm and presented it in pseudocode.

A new solution
After reading all the answers, and doing some experiments, I found that for a range of integer from 1 to 10ⁿ-1:

• For digits 1 to 9, n*10^(n-1) pieces are needed
• For digit 0, if not using leading zeros, n*10^n-1 - ((10ⁿ-1) / 9) are needed
• For digit 0, if using leading zeros, n*10^n-1 - n are needed

The first formula was found by strainer (and probably by others), and I found the other two by trial and error (but they may be included in other answers).

For example, if n = 6, range is 1 to 999,999:

• For digits 1 to 9 we need 6*10⁵ = 600,000 of each one
• For digit 0, without leading zeros, we need 6*10⁵ – (10⁶-1)/9 = 600,000 - 111,111 = 488,889
• For digit 0, with leading zeros, we need 6*10⁵ – 6 = 599,994

These numbers can be checked using High-Performance Mark results.

Using these formulas, I improved the original algorithm. It still loops from the first to the last number in the range of integers, but, if it finds a number which is a power of ten, it uses the formulas to add to the digits count the quantity for a full range of 1 to 9 or 1 to 99 or 1 to 999 etc. Here's the algorithm in pseudocode:

integer First,Last //First and last number in the range
integer Number     //Current number in the loop
integer Power      //Power is the n in 10^n in the formulas
integer Nines      //Nines is the resut of 10^n - 1, 10^5 - 1 = 99999
integer Prefix     //First digits in a number. For 14,200, prefix is 142
array 0..9  Digits //Will hold the count for all the digits

FOR Number = First TO Last
  CALL TallyDigitsForOneNumber WITH Number,1  //Tally the count of each digit 
                                              //in the number, increment by 1
  //Start of optimization. Comments are for Number = 1,000 and Last = 8,000.
  Power = Zeros at the end of number //For 1,000, Power = 3
  IF Power > 0                       //The number ends in 0 00 000 etc 
    Nines = 10^Power-1                 //Nines = 10^3 - 1 = 1000 - 1 = 999
    IF Number+Nines <= Last            //If 1,000+999 < 8,000, add a full set
      Digits[0-9] += Power*10^(Power-1)  //Add 3*10^(3-1) = 300 to digits 0 to 9
      Digits[0]   -= -Power              //Adjust digit 0 (leading zeros formula)
      Prefix = First digits of Number    //For 1000, prefix is 1
      CALL TallyDigitsForOneNumber WITH Prefix,Nines //Tally the count of each 
                                                     //digit in prefix,
                                                     //increment by 999
      Number += Nines                    //Increment the loop counter 999 cycles
    ENDIF
  ENDIF 
  //End of optimization
ENDFOR  

SUBROUTINE TallyDigitsForOneNumber PARAMS Number,Count
  REPEAT
    Digits [ Number % 10 ] += Count
    Number = Number / 10
  UNTIL Number = 0

For example, for range 786 to 3,021, the counter will be incremented:

• By 1 from 786 to 790 (5 cycles)
• By 9 from 790 to 799 (1 cycle)
• By 1 from 799 to 800
• By 99 from 800 to 899
• By 1 from 899 to 900
• By 99 from 900 to 999
• By 1 from 999 to 1000
• By 999 from 1000 to 1999
• By 1 from 1999 to 2000
• By 999 from 2000 to 2999
• By 1 from 2999 to 3000
• By 1 from 3000 to 3010 (10 cycles)
• By 9 from 3010 to 3019 (1 cycle)
• By 1 from 3019 to 3021 (2 cycles)

Total: 28 cycles Without optimization: 2,235 cycles

Note that this algorithm solves the problem without leading zeros. To use it with leading zeros, I used a hack:

If range 700 to 1,000 with leading zeros is needed, use the algorithm for 10,700 to 11,000 and then substract 1,000 - 700 = 300 from the count of digit 1.

Benchmark and Source code

I tested the original approach, the same approach using %10 and the new solution for some large ranges, with these results:

Original             104.78 seconds
With %10              83.66
With Powers of Ten     0.07

A screenshot of the benchmark application:

If you would like to see the full source code or run the benchmark, use these links:

• Complete Source code (in Clarion): http://sca.mx/ftp/countdigits.txt
• Compilable project and win32 exe: http://sca.mx/ftp/countdigits.zip

Accepted answer

noahlavine solution may be correct, but l just couldn’t follow the pseudo code, I think there are some details missing or not completely explained.

Aaronaught solution seems to be correct, but the code is just too complex for my taste.

I accepted strainer’s answer, because his line of thought guided me to develop this new solution.

Answer 1

You can separate each digit (look here for a example), create a histogram with entries from 0..9 (which will count how many digits appeared in a number) and multiply by the number of 'numbers' asked.

But if isn't what you are looking for, can you give a better example?

Edited:

Now I think I got the problem. I think you can reckon this (pseudo C):

int histogram[10];
memset(histogram, 0, sizeof(histogram));

for(i = startNumber; i <= endNumber; ++i)
{
    array = separateDigits(i);
    for(j = 0; k < array.length; ++j)
    {
        histogram[k]++;
    }
}

Separate digits implements the function in the link.

Each position of the histogram will have the amount of each digit. For example

histogram[0] == total of zeros
histogram[1] == total of ones

...

Regards

Answer 2

I'm assuming you want a solution where the numbers are in a range, and you have the starting and ending number. Imagine starting with the start number and counting up until you reach the end number - it would work, but it would be slow. I think the trick to a fast algorithm is to realize that in order to go up one digit in the 10^x place and keep everything else the same, you need to use all of the digits before it 10^x times plus all digits 0-9 10^(x-1) times. (Except that your counting may have involved a carry past the x-th digit - I correct for this below.)

Here's an example. Say you're counting from 523 to 1004.

• First, you count from 523 to 524. This uses the digits 5, 2, and 4 once each.
• Second, count from 524 to 604. The rightmost digit does 6 cycles through all of the digits, so you need 6 copies of each digit. The second digit goes through digits 2 through 0, 10 times each. The third digit is 6 5 times and 5 100-24 times.
• Third, count from 604 to 1004. The rightmost digit does 40 cycles, so add 40 copies of each digit. The second from right digit doers 4 cycles, so add 4 copies of each digit. The leftmost digit does 100 each of 7, 8, and 9, plus 5 of 0 and 100 - 5 of 6. The last digit is 1 5 times.

To speed up the last bit, look at the part about the rightmost two places. It uses each digit 10 + 1 times. In general, 1 + 10 + ... + 10^n = (10^(n+1) - 1)/9, which we can use to speed up counting even more.

My algorithm is to count up from the start number to the end number (using base-10 counting), but use the fact above to do it quickly. You iterate through the digits of the starting number from least to most significant, and at each place you count up so that that digit is the same as the one in the ending number. At each point, n is the number of up-counts you need to do before you get to a carry, and m the number you need to do afterwards.

Now let's assume pseudocode counts as a language. Here, then, is what I would do:

convert start and end numbers to digit arrays start[] and end[]
create an array counts[] with 10 elements which stores the number of copies of
     each digit that you need

iterate through start number from right to left. at the i-th digit,
    let d be the number of digits you must count up to get from this digit
        to the i-th digit in the ending number. (i.e. subtract the equivalent
        digits mod 10)
    add d * (10^i - 1)/9 to each entry in count.
    let m be the numerical value of all the digits to the right of this digit,
        n be 10^i - m.
    for each digit e from the left of the starting number up to and including the
        i-th digit, add n to the count for that digit.
    for j in 1 to d
        increment the i-th digit by one, including doing any carries
        for each digit e from the left of the starting number up to and including
            the i-th digit, add 10^i to the count for that digit
    for each digit e from the left of the starting number up to and including the
        i-th digit, add m to the count for that digit.
    set the i-th digit of the starting number to be the i-th digit of the ending
        number.

Oh, and since the value of i increases by one each time, keep track of your old 10^i and just multiply it by 10 to get the new one, instead of exponentiating each time.

Answer 3

Your approach is fine. I'm not sure why you would ever need anything faster than what you've described.

Or, this would give you an instantaneous solution: Before you actually need it, calculate what you would need from 1 to some maximum number. You can store the numbers needed at each step. If you have a range like your second example, it would be what's needed for 1 to 300, minus what's needed for 1 to 50.

Now you have a lookup table that can be called at will. Doing up to 10,000 would only take a few MB and, what, a few minutes to compute, once?

Answer 4

This doesn't answer your exact question, but it's interesting to note the distribution of first digits according to Benford's Law. For example, if you choose a set of numbers at random, 30% of them will start with "1", which is somewhat counter-intuitive.

I don't know of any distributions describing subsequent digits, but you might be able to determine this empirically and come up with a simple formula for computing an approximate number of digits required for any range of numbers.

Answer 5

If "better" means "clearer," then I doubt it. If it means "faster," then yes, but I wouldn't use a faster algorithm in place of a clearer one without a compelling need.

#!/usr/bin/ruby1.8

def digits_for_range(min, max, leading_zeros)
  bins = [0] * 10
  format = [
    '%',
    ('0' if leading_zeros),
    max.to_s.size,
    'd',
  ].compact.join
  (min..max).each do |i|
    s = format % i
    for digit in s.scan(/./)
      bins[digit.to_i] +=1  unless digit == ' '
    end
  end
  bins
end

p digits_for_range(1, 49, false) 
# => [4, 15, 15, 15, 15, 5, 5, 5, 5, 5]

p digits_for_range(1, 49, true)
# => [13, 15, 15, 15, 15, 5, 5, 5, 5, 5]

p digits_for_range(1, 10000, false)
# => [2893, 4001, 4000, 4000, 4000, 4000, 4000, 4000, 4000, 4000]

Ruby 1.8, a language known to be "dog slow," runs the above code in 0.135 seconds. That includes loading the interpreter. Don't give up an obvious algorithm unless you need more speed.

Answer 6

I asked this question on Math Overflow, and got spanked for asking such a simple question. One of the users took pity on me and said if I posted it to The Art of Problem Solving, he would answer it; so I did.

Here is the answer he posted:
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=1741600#1741600

Embarrassingly, my math-fu is inadequate to understand what he posted (the guy is 19 years old...that is so depressing). I really need to take some math classes.

On the bright side, the equation is recursive, so it should be a simple matter to turn it into a recursive function with a few lines of code, by someone who understands the math.

Answer 7

To reel of the digits from a number, we'd only ever need to do a costly string conversion if we couldnt do a mod, digits can most quickly be pushed of a number like this:

feed=number;
do
{ digit=feed%10;
  feed/=10; 
  //use digit... eg. digitTally[digit]++;
  }
while(feed>0)

that loop should be very fast and can just be placed inside a loop of the start to end numbers for the simplest way to tally the digits.

To go faster, for larger range of numbers, im looking for an optimised method of tallying all digits from 0 to number*10^significance (from a start to end bazzogles me)

here is a table showing digit tallies of some single significant digits.. these are inclusive of 0, but not the top value itself, -that was an oversight but its maybe a bit easier to see patterns (having the top values digits absent here) These tallies dont include trailing zeros,

  1 10 100 1000 10000 2 20 30 40 60 90 200 600 2000  6000

0 1 1  10  190  2890  1  2  3  4  6  9  30 110  490  1690
1 0 1  20  300  4000  1 12 13 14 16 19 140 220 1600  2800
2 0 1  20  300  4000  0  2 13 14 16 19  40 220  600  2800
3 0 1  20  300  4000  0  2  3 14 16 19  40 220  600  2800
4 0 1  20  300  4000  0  2  3  4 16 19  40 220  600  2800
5 0 1  20  300  4000  0  2  3  4 16 19  40 220  600  2800
6 0 1  20  300  4000  0  2  3  4  6 19  40 120  600  1800
7 0 1  20  300  4000  0  2  3  4  6 19  40 120  600  1800
8 0 1  20  300  4000  0  2  3  4  6 19  40 120  600  1800
9 0 1  20  300  4000  0  2  3  4  6  9  40 120  600  1800

edit: clearing up my origonal thoughts:

from the brute force table showing tallies from 0 (included) to poweroTen(notinc) it is visible that a majordigit of tenpower:

increments tally[0 to 9] by md*tp*10^(tp-1)
increments tally[1 to md-1] by 10^tp
decrements tally[0] by (10^tp - 10) 
(to remove leading 0s if tp>leadingzeros)
can increment tally[moresignificantdigits] by self(md*10^tp) 
(to complete an effect)

if these tally adjustments were applied for each significant digit, the tally should be modified as though counted from 0 to end-1

the adjustments can be inverted to remove preceeding range (start number)

Thanks Aaronaught for your complete and tested answer.

Answer 8

Hi

Here's a very bad answer, I'm ashamed to post it. I asked Mathematica to tally the digits used in all numbers from 1 to 1,000,000, no leading 0s. Here's what I got:

0   488895
1   600001
2   600000
3   600000
4   600000
5   600000
6   600000
7   600000
8   600000
9   600000

Next time you're ordering sticky digits for selling in your hardware store, order in these proportions, you won't be far wrong.

Regards

Mark

Answer 9

There's a clear mathematical solution to a problem like this. Let's assume the value is zero-padded to the maximum number of digits (it's not, but we'll compensate for that later), and reason through it:

• 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)

The obvious pattern for any given digit, if the range is from 0 to a power of 10, is N * 10^N-1, where N is the power of 10.

What if the range is not a power of 10? Start with the lowest power of 10, then work up. The easiest case to deal with is a maximum like 399. We know that for each multiple of 100, each digit occurs at least 20 times, but we have to compensate for the number of times it appears in the most-significant-digit position, which is going to be exactly 100 for digits 0-3, and exactly zero for all other digits. Specifically, the extra amount to add is 10^N for the relevant digits.

Putting this into a formula, for upper bounds that are 1 less than some multiple of a power of 10 (i.e. 399, 6999, etc.) it becomes: M * N * 10^N-1 + iif(d <= M, 10^N, 0)

Now you just have to deal with the remainder (which we'll call R). Take 445 as an example. This is whatever the result is for 399, plus the range 400-445. In this range, the MSD occurs R more times, and all digits (including the MSD) also occur at the same frequencies they would from range [0 - R].

Now we just have to compensate for the leading zeros. This pattern is easy - it's just:

10^N + 10^N-1 + 10^N-2 + ... + **10⁰

Update: This version correctly takes into account "padding zeros", i.e. the zeros in middle positions when dealing with the remainder ([4*0*0, 4*0*1, 4*0*2, ...]). Figuring out the padding zeros is a bit ugly, but the revised code (C-style pseudocode) handles it:

function countdigits(int d, int low, int high) {
    return countdigits(d, low, high, false);
}

function countdigits(int d, int low, int high, bool inner) {
    if (high == 0)
        return (d == 0) ? 1 : 0;

    if (low > 0)
        return countdigits(d, 0, high) - countdigits(d, 0, low);

    int n = floor(log10(high));
    int m = floor((high + 1) / pow(10, n));
    int r = high - m * pow(10, n);
    return
        (max(m, 1) * n * pow(10, n-1)) +                             // (1)
        ((d < m) ? pow(10, n) : 0) +                                 // (2)
        (((r >= 0) && (n > 0)) ? countdigits(d, 0, r, true) : 0) +   // (3)
        (((r >= 0) && (d == m)) ? (r + 1) : 0) +                     // (4)
        (((r >= 0) && (d == 0)) ? countpaddingzeros(n, r) : 0) -     // (5)
        (((d == 0) && !inner) ? countleadingzeros(n) : 0);           // (6)
}

function countleadingzeros(int n) {
    return (n == 0) ? 1 : pow(10, n) * countleadingzeros(n - 1);
}

function countpaddingzeros(int n, int r) {
    return (r + 1) * max(0, n - max(0, floor(log10(r))) - 1);
}

As you can see, it's gotten a bit uglier but it still runs in O(log n) time, so if you need to handle numbers in the billions, this will still give you instant results. :-) And if you run it on the range [0 - 1000000], you get the exact same distribution as the one posted by High-Performance Mark, so I'm almost positive that it's correct.

FYI, the reason for the inner variable is that the leading-zero function is already recursive, so it can only be counted in the first execution of countdigits.

Update 2: In case the code is hard to read, here's a reference for what each line of the countdigits return statement means (I tried inline comments but they made the code even harder to read):

1. Frequency of any digit up to highest power of 10 (0-99, etc.)
2. Frequency of MSD above any multiple of highest power of 10 (100-399)
3. Frequency of any digits in remainder (400-445, R = 45)
4. Additional frequency of MSD in remainder
5. Count zeros in middle position for remainder range (404, 405...)
6. Subtract leading zeros only once (on outermost loop)