Programming Praxis

7 Responses to “Counting Digits”

1. matthew said

   January 7, 2020 at 4:28 PM

   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

   January 7, 2020 at 5:06 PM

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

   January 7, 2020 at 8:07 PM

   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

   January 7, 2020 at 8:27 PM

   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

   January 8, 2020 at 2:11 PM

   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)
   
6. Steve said

   January 8, 2020 at 2:13 PM

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

   March 19, 2020 at 3:49 AM

   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}