LeetCode 233 | Number of Digit One | JavaScript
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
Example 1:
Input: n = 13
Output: 6
Example 2:
Input: n = 0
Output: 0
Learn how to count the number of times the digit '1' appears from 1 to N in JavaScript using an optimized mathematical approach.
In this video, we cover:
A simple brute-force solution
An efficient formula-based approach
Step-by-step explanation with examples
The optimized version counts the number of times the digit '1' appears from 1 to n using digit position analysis, which is much faster than iterating every number.
How It Works
The algorithm examines each digit position—units, tens, hundreds, etc.—by looping with i as powers of 10 up to n (e.g., 1, 10, 100, ...).
For each position, it calculates:
How many full cycles of that digit position are present (using integer division).
Partial cycles accounting for the remainder (using modulus math).
It adds up the count of '1's at each digit position to get the total.
Core Formula Breakdown
For each digit place (i):
Math.floor(n / (i * 10)) * i counts full sets where '1' appears in this position.
Math.min(Math.max(n % (i * 10) - i + 1, 0), i) counts the remaining occurrences in incomplete (partial) group at that position.
Example: n = 13
Units Place (i = 1)
Full sets: Math.floor(13 / 10) * 1 = 1
Partial: Math.min(Math.max(13 % 10 - 1 + 1, 0), 1) = Math.min(Math.max(3, 0), 1) = 1
Total for units: 2
Tens Place (i = 10)
Full sets: Math.floor(13 / 100) * 10 = 0
Partial: Math.min(Math.max(13 % 100 - 10 + 1, 0), 10) = Math.min(Math.max(4, 0), 10) = 4
Total for tens: 4
Total occurrences: 2 (units) + 4 (tens) = 6
Why It's Fast
The number of iterations equals the number of digit places in n (so, log₁₀n).
Avoids converting numbers to strings and looping through all numbers, saving a lot of time for large n.
Key Advantages
Time efficiency: Approximately O(log n)
Scalability: Works well for very large values of n
Mathematical accuracy: Counts per digit place instead of per number