LC-0233 Hard LeetCode

233. Number of Digit One

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 36% Topics: Math, Dynamic Programming, Recursion

Reading material

Math & Geometry 12 min 1-D Dynamic Programming 16 min Backtracking 14 min

Reference solution (spoiler · python)

# Time:  O(logn)
# Space: O(1)

class Solution(object):
    def countDigitOne(self, n):
        """
        :type n: int
        :rtype: int
        """
        DIGIT = 1
        is_zero = int(DIGIT == 0)
        result = is_zero
        base = 1
        while n >= base:
            result += (n//(10*base)-is_zero)*base + \
                      min(base, max(n%(10*base) - DIGIT*base + 1, 0))
            base *= 10
        return result

Solution from kamyu104/LeetCode-Solutions · MIT