*

*Obviously this can be applied to numbers less than -1 as well.*

This realisation stood to me recently when I was trying to figure out the number of times a digit would have appeared between 0 and n. My first step was to calculate how many digits there are in total between 0 and 99: 10 * 1 + 90 * 2 = 190. That would mean that each digit appears 19 times. When I calculated this for a specific digit though I realised that it should be twenty. Each number appears 10 times in the unit column and ten times in the tens column - for two that would be the ten numbers from 20-29. I had forgotten the leading 0. 0-9 should have been 00-99 - or if I was working with a three-digit number 000-009.

Once I made this observation a pattern began to emerge:

I will work with 11x22 where x is some digit. Left is the number to the left of the x and right is the number to the right of x. Since we are working with the hundred column we will be working in hundreds - I will call this the score. Let us say we are searching for the total occurrences of 5.

The important thing to note is that the the third column will not have a five until we reach five hundred and then its total will increase by 1 for every number until 599. The total will stay at 100 until we reach 1599, where the process will repeat again.

Therefore, where x is less than five, for example 11022 we can calculate the number of times x has occurred in that column using left * score = 1100.

Where x is greater than five, for example 11622, we have gone through the 500's one extra time so our total is (left + 1) * score = 1200.

Finally, when the digit is equal to five, for example 11522, we have the total for less than but need to add in from 11500 to 11522. This last part is given by 'right + 1' so the total is given by left * score + right + 1 = 1123.

Here is some sample output (the last two numbers are the total for this method and a brute force method):

Searching for total occurrences of 5 in numbers up to 14527

Order: 1 New Target: 14527

Digit: 7 Left: 1452 Right: 0

calculate greater than 1453

Order: 10 New Target: 1452

Digit: 2 Left: 145 Right: 7

calculate less than 1450

Order: 100 New Target: 145

Digit: 5 Left: 14 Right: 27

calculate equal 1428

Order: 1000 New Target: 14

Digit: 4 Left: 1 Right: 527

calculate less than 1000

Order: 10000 New Target: 1

Digit: 1 Left: 0 Right: 4527

calculate less than 0

5331 5331

## No comments:

## Post a Comment