Number of Digit One - Video Solutions

Problem Overview: Given an integer n, count how many times the digit 1 appears in all numbers from 1 to n. Instead of generating every number explicitly, the challenge is recognizing patterns in how the digit 1 appears across decimal positions.

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

The simplest strategy is to iterate through every number from 1 to n. For each number, repeatedly extract digits using modulo and division (% 10, / 10) and count how many digits equal 1. Each number has at most log10(n) digits, which leads to a total time complexity of O(n log n). Space remains O(1) since you only maintain a counter. This approach is straightforward and good for validating logic, but it becomes too slow when n approaches large limits (for example up to billions).

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

The efficient solution analyzes each decimal position independently. For a given digit position (ones, tens, hundreds, etc.), determine how many full cycles of 0–9 occur and how the remainder contributes extra occurrences of 1. For position value m (1, 10, 100...), split n into three parts: high = n / (m * 10), current = (n / m) % 10, and low = n % m. The number of ones contributed by that position depends on the value of current. If it is 0, only the completed cycles contribute; if it is 1, add low + 1; if it is greater than 1, add an extra full cycle. Iterate through all digit positions until m > n. This works because digit distributions repeat predictably in base‑10 counting.

This positional counting technique effectively performs a lightweight digit analysis rather than enumerating numbers. It relies on mathematical patterns in decimal representation, which is why the complexity drops to O(log n) time with constant space. The idea appears in many digit‑analysis problems and is closely related to concepts used in math problems and some forms of dynamic programming or recursion based digit DP.

Recommended for interviews: Interviewers expect the digit‑position counting solution. The brute force method shows you understand the problem definition, but the O(log n) positional counting approach demonstrates the pattern recognition and mathematical reasoning required for hard problems.