Problem
Given an integern, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
Examples
Constraints
- 0 <= n <= 10<sup>9</sup>
Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 233 with 35 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 233 # by problem number
lcpy gen -s number_of_digit_one # by problem name
n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
Input: n = 13
Output: 6
Input: n = 0
Output: 0
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
| Time | Space |
|---|---|
| O(log10(n)) | O(1) |