Count Digit One

Problem

Count how many times the digit 1 appears in all numbers from 0 through n inclusive.

For every decimal position, split n into the higher part, the current digit and the lower part, and count ones contributed at that position: high times factor for current 0, high times factor plus low plus 1 for current 1, and high plus one times factor for larger digits.

Hint

The three cases for the current digit handle how many complete or partial cycles of the position are included.

Test cases

case 1

in: [0]

expected: 0

case 2

in: [13]

expected: 6

case 3

in: [100]

expected: 21

case 4

in: [1000]

expected: 301

case 5

in: [20]

expected: 12

Starter codePython

def count_digit_one(n):
    # Your code here
    pass

5 test cases · run your code against them in the editor