Counting Digits
January 7, 2020
We have a simple homework question today:
Given a range of non-negative integers, count the number of 2s, 5s and 8s in the decimal representations of the digits. For instance, from 295 to 305, there are 9:
295: 2 296: 1 297: 1 298: 2 299: 1 300: 0 301: 0 302: 1 303: 0 304: 0 305: 1 Total 9
Your task is to write a program to count the 2, 5, and 8 digits in the range of integers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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)) # 9That needs some modification for digit ‘0’ (an exercise for the reader)- also the while condition can be ‘n > m’
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 countOr 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])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 ; +/{...{...}... - Return total sum of hits ; {+/...}(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)Klong results:
{+/{[n];n::x;+/{#($n)?$x}'”258″}’x+!1+y-x}(295;305)
9
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}