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.

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
    ; +/{...{...}...                 - 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

    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}
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: