Number of Digit One Python Solution with Tests

Tested Python solution for LeetCode 233 with 35 pytest cases. Generate a practice environment with lcpy.

LeetCode 233, Hard. Topics: Math, Dynamic Programming, Recursion. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 35 parametrized pytest cases, and a playground notebook:

lcpy gen -n 233   # by problem number
lcpy gen -s number_of_digit_one   # by problem name

​

Problem

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

​

Examples

Input: n = 13
Output: 6

Input: n = 0
Output: 0

​

Constraints

• 0 <= n <= 10⁹

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(log10(n))
    # Space: O(1)
    def count_digit_one(self, n: int) -> int:
        total = 0
        place = 1
        while place <= n:
            high = n // (place * 10)
            cur = (n // place) % 10
            low = n % place
            if cur == 0:
                total += high * place
            elif cur == 1:
                total += high * place + low + 1
            else:
                total += (high + 1) * place
            place *= 10
        return total

​

Complexity

Time	Space
O(log10(n))	O(1)

​

Tags