## Counting Digits

### January 7, 2020

Here’s our solution:

```(define (f lo hi)
(define (is258 d) (or (= d 2) (= d 5) (= d 8)))
(define (cnt n) (length (filter is258 (digits n))))
(do ((n lo (+ n 1)) (c 0 (+ c (cnt n)))) ((< hi n) c))) > (f 295 395)
9
> (time (f 11 100000))
(time (f 11 ...))
2 collections
0.018759638s elapsed cpu time, including 0.000229760s collecting
0.018892309s elapsed real time, including 0.000238270s collecting
9539376 bytes allocated, including 16834208 bytes reclaimed
149997```

You can run the program at https://ideone.com/FA3ADI.

Pages: 1 2

### 7 Responses to “Counting Digits”

1. matthew said

Happy new year & I hope everyone enjoyed the holiday break.

I thought that should be a more direct way of counting the digits than enumerating the entire range. For simplicity, dcount counts all the digits in range(n) – ie. not including n itself:

```def dcount(digits,n):
count = 0
m,m1 = 1,10
while n >= m:
for k in digits:
count += n//m1*m + min(m,max(n%m1-k*m,0))
m,m1 = m1,10*m1
return count

digits = [2,5,8]

print(dcount(digits,306)-dcount(digits,295)) # 9
```
2. matthew said

That needs some modification for digit ‘0’ (an exercise for the reader)- also the while condition can be ‘n > m’

3. matthew said

This is better (and the ‘0’ count is correct if we assume numbers are zero padded on the left to the same length):

```def dcount(digits,n):
count = 0
m,m1 = 1,10
for _ in range(len(str(n-1))):
count += n//m1*m*len(digits)
for k in digits: count += min(m,max(n%m1-k*m,0))
m,m1 = m1,10*m1
return count
```
4. matthew said

Or wrap the whole thing up in a list comprehension:

```def dcount(digits,n):
return sum(sum(n//m1*m + min(m,max(n%m1-k*m,0)) for k in digits)
for i in range(len(str(n-1))) for m in [10**i] for m1 in [10*m])
```
5. Steve said

Klong version

```; \$n                             - Change number to string
; (\$n)?\$x                        - Turn digit into string and store in a list the positions of digit in string
; #(\$n)?\$x                       - Get number of positions
; {#(\$n)?\$x}'"258"}              - Function to do the aboved for each digit in "258" and return list of number of positions/hits
; +/...                          - Return sum of hits
; {[n];n::x;+/{...}...}'x+!1+y-x - Function to goo through each of the number in the range and run the inner function, returning a list of sums
; {+/...}(295;305)               - Run middle function ({}) with first and last number in range of numbers
;
{+/{[n];n::x;+/{#(\$n)?\$x}'"258"}'x+!1+y-x}(295;305)
```
6. Steve said

Klong results:
{+/{[n];n::x;+/{#(\$n)?\$x}'”258″}’x+!1+y-x}(295;305)
9

7. Daniel said

Here’s a solution in Python, based on the digit counting algorithm from here.

```from collections import Counter

def count_digits(lo, hi):
assert 0 <= lo <= hi
counts = Counter()
x = lo
while x <= hi:
digits = [int(c) for c in str(x)]
counts += Counter(digits)
power = len(str(x)) - len(str(x).rstrip('0'))
if power > 0:
nines = 10 ** power - 1
if x + nines <= hi:
counts += Counter(dict.fromkeys(range(10), power * 10 ** (power - 1)))
counts[0] -= power
prefix = [int(c) for c in str(x).rstrip('0')]
for digit in prefix:
counts[digit] += nines
x += nines
x += 1
return dict(counts)

def count_258(lo, hi):
return sum(count for digit, count in count_digits(lo, hi).items() if digit in (2, 5, 8))

print(count_258(295, 305))
print(count_258(295_000_000_000, 305_000_000_000))
print(count_digits(0, 99))
```

Output:

```9
35000000001
{0: 10, 1: 20, 2: 20, 3: 20, 4: 20, 5: 20, 6: 20, 7: 20, 8: 20, 9: 20}
```