Number Of Digit One - Leetcode Solution

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

Example:

Input: 13 Output: 6 Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Solution:

Approach: The problem can be solved using mathematics calculations and a bit of observation. We will be using a digit by digit approach to count the number of ones.

Step 1: Convert the given number to a string to examine each digit in the number.

Step 2: We need to calculate the number of ones in each digit place (1s, 10s, 100s, etc.) separately.

Step 3: We will consider the example of the number 3456. For the 1s place, we will use the following formula: (345/10)*1 + min(max(345%10 - 1 + 1, 0), 1) = (34)*1 + min(max(5 - 1 + 1, 0), 1) = 34+1 = 35.

• We divide 345 by 10 to get the quotient 34, which tells us how many times the digit one appears in the 1s place for the numbers less than or equal to 345.

• The min(max(345%10 - 1 + 1, 0), 1) gives us the extra ones that appear in the number 345 specifically.

• 345%10 gives us the digit in the 1s place, which is 5.

• We subtract 1 from it, so we can count the ones less than or equal to the digit in the 1s place.

• We then add 1 to the result to count the ones at the digit in the 1s place itself, but only if this result is less than 2, otherwise we only count 1.

Step 4: Similarly, for the 10s place, we will use the following formula: (34/10)*10 + min(max(34%10 - 1 + 1, 0), 10) = 30 + 5 = 35.

• We divide 34 by 10 to get the quotient 3, which tells us how many times the digit one appears in the 10s place for the numbers less than or equal to 345.

• The min(max(34%10 - 1 + 1, 0), 10) gives us the extra ones that appear in the number 345 specifically.

• 34%10 gives us the digit in the 10s place, which is 4.

• We subtract 1 from it, so we can count the ones less than or equal to the digit in the 10s place (i.e., number of ones in the "10s" multiples).

• We then add 1 to the result to count the ones at the digit in the 10s place itself.

Step 5: We continue this process for each digit place (100s, 1000s, etc.) until we have counted all the ones in the number.

Step 6: Add up all the ones we've counted to get the total number of ones.

Code implementation:

class Solution:
    def countDigitOne(self, n: int) -> int:
        count, factor = 0, 1
        while factor <= n:
            count += (n // (factor * 10)) * factor + min(max(n % (factor * 10) - factor + 1, 0), factor)
            factor *= 10
        return count

Time Complexity: The time complexity of the above solution is O(logn).

Space Complexity: The space complexity of the above solution is O(1).

1