Number of Digit One

Problem Description

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

Key Insights

• The problem requires counting occurrences of the digit '1' across a range of numbers.
• A direct approach iterating through all numbers up to n is inefficient due to the constraints (n can be as large as 10^9).
• A mathematical approach that considers each digit's contribution to the count can efficiently solve the problem.
• The counting can be done by analyzing each digit position (units, tens, hundreds, etc.) and calculating how many times '1' appears in that position across the entire range.

Space and Time Complexity

Time Complexity: O(log n) - The number of digits in n determines the number of iterations. Space Complexity: O(1) - Only a constant amount of space is used.

Solution

To solve the problem, we analyze each digit of the number n and calculate how many times the digit '1' appears in that specific position. We can break down the number into three parts: the higher digits, the current digit, and the lower digits. Based on these, we can derive the count of '1's contributed by that digit position.

1. For each digit position, calculate:

   • The higher part of the number (digits left of the current position).
   • The current digit itself.
   • The lower part of the number (digits right of the current position).

2. Depending on the value of the current digit:

   • If it's greater than 1, the contribution includes all combinations from the higher part.
   • If it's exactly 1, the contribution includes all combinations from the higher part plus the numbers formed by the lower part.
   • If it's less than 1, the contribution comes only from the higher part.

3. Sum the contributions from all digit positions.

Code Solutions