Number of Digit One - Video Solutions

Problem Overview: Given an integer n, count how many times the digit 1 appears in all non‑negative integers from 0 to n. Instead of generating every number, the challenge is recognizing patterns in how digits repeat across positions.

Approach 1: Brute Force Enumeration (Time: O(n log n), Space: O(1))

The straightforward idea is to iterate through every integer from 1 to n, convert each number into digits, and count how many times the digit 1 appears. You can extract digits using modulo and division (num % 10, num /= 10) or convert the number to a string and scan it. The complexity grows quickly because every number may contain up to log10(n) digits, making the total work roughly O(n log n). This approach works for small values of n but becomes far too slow when n reaches millions or billions.

Approach 2: Counting by Digit Position (Time: O(log n), Space: O(1))

The optimal solution analyzes each digit position independently. For every position (ones, tens, hundreds, etc.), calculate how many full cycles of numbers contribute a 1 at that position. For a given position value factor = 1, 10, 100..., split the number into three parts: higher digits to the left, the current digit, and lower digits to the right. The count contributed by that position depends on the current digit:

If the current digit is 0, the number of ones comes entirely from completed cycles (higher * factor). If the current digit is 1, add the remaining numbers in the partial cycle (higher * factor + lower + 1). If the current digit is greater than 1, a full additional cycle contributes ((higher + 1) * factor). Iterating through digit positions requires only log10(n) steps, which reduces the time complexity to O(log n). This method relies on simple arithmetic and pattern observation rather than explicit enumeration, making it highly efficient for large inputs.

The technique is a classic example of digit decomposition used in math problems involving ranges of numbers. The reasoning process resembles state transitions seen in dynamic programming problems and can also be implemented recursively using recursion to process digit ranges.

Recommended for interviews: Interviewers expect the digit-position counting approach. Starting with the brute force method shows you understand the problem definition, but quickly moving to the mathematical pattern demonstrates algorithmic maturity. The O(log n) solution is the standard optimal answer and scales easily to very large values of n.