Number of Digit One solution and explanation
Google
9 more videos on this problem
Leetcode 233(Hard) Number of Digit One: Simple C++ SolutionShivam Patel · 23:42 · 11K views
Number of Digit One - Asked in Microsoft, Google, Adobe!HackerEarth · 8:43 · 9K views
Digit DP Tutorial | Ep - 02 | 233. Number of Digit One | Dynamic Programming | C++ | By Aman BabuAman Babu · 8:23 · 8K views
LeetCode 233. Number of Digit One Explanation and Solutionhappygirlzt · 10:31 · 7K views
L-02. Digit DP | Number Of Digit One | Leetcode 233 | Recursive + Memoization | Intuition + CodeWhy Not DP [By Piyush Raj] · 25:28 · 5K views
233. Number of Digit One (Leetcode Hard)Programming Live with Larry · 40:58 · 1K views
233. Number of Digit One - Daily Leetcode (Day 41)yeetcode · 19:36 · 1K views
Leetcode Question 233 "Number of Digit One" in JavaGhumman Tech · 5:48 · 1K views
LeetCode 233. Number of Digit One 中文解释 Chinese Versionhappygirlzt · 9:55 · 1K views
Leetcode 233: Number of Digit One | Recursion | Intuition and ApproachCode Concepts with Animesh · 23:39 · 1K views
The problem
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
Constraints:
0 <= n <= 109
Approach overview
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.
Approach 1: Brute Force Approach
In this approach, we iterate through each number from 0 to n. For each number, we count the number of times digit 1 appears. Although this approach is simple, it's not optimal for large values of n due to its high time complexity.
def countDigitOne(n: int) -> int:
count = 0
for i in range(1, n + 1):
count += str(i).count('1')
return count
n = 13
print(countDigitOne(n))public class Main {
public static int countDigitOne(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
int num = i;
while (num > 0) {
if (num % 10 == 1) count++;
num /= 10;
}
}
return count;
}
public static void main(String[] args) {
int n = 13;
System.out.println(countDigitOne(n));
}
}#include <iostream>
using namespace std;
int countDigitOne(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
int num = i;
while (num > 0) {
if (num % 10 == 1) count++;
num /= 10;
}
}
return count;
}
int main() {
int n = 13;
cout << countDigitOne(n) << endl;
return 0;
}function countDigitOne(n) {
let count = 0;
for (let i = 1; i <= n; i++) {
let num = i;
while (num > 0) {
if (num % 10 === 1) count++;
num = Math.floor(num / 10);
}
}
return count;
}
const n = 13;
console.log(countDigitOne(n));#include <stdio.h>
int countDigitOne(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
int num = i;
while (num > 0) {
if (num % 10 == 1) count++;
num /= 10;
}
}
return count;
}
int main() {
int n = 13;
printf("%d\n", countDigitOne(n));
return 0;
}using System;
class Program {
static int CountDigitOne(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
int num = i;
while (num > 0) {
if (num % 10 == 1) count++;
num /= 10;
}
}
return count;
}
static void Main() {
int n = 13;
Console.WriteLine(CountDigitOne(n));
}
}This Python code converts each number to a string and uses the count method to find occurrences of '1'.
Time Complexity: O(n * log10(n)), accounting for string conversion and counting.
Space Complexity: O(1), as additional space used is minimal.
Approach 2: Counting by Digit Position
This optimized approach examines digit positions and calculates how many times 1 appears at each position up to n. It leverages the structure of numbers and is more efficient for large values of n.
def countDigitOne(n: int) -> int:
count = 0
i = 1
while i <= n:
divider = i * 10
count += (n // divider) * i + min(max(n % divider - i + 1, 0), i)
i *= 10
return count
n = 13
print(countDigitOne(n))public class Main {
public static int countDigitOne(int n) {
int count = 0;
for (long i = 1; i <= n; i *= 10) {
long divider = i * 10;
count += (n / divider) * i + ((n % divider >= i) ? (n % divider - i + 1) : 0);
}
return count;
}
public static void main(String[] args) {
int n = 13;
System.out.println(countDigitOne(n));
}
}#include <iostream>
using namespace std;
int countDigitOne(int n) {
int count = 0;
for (long long i = 1; i <= n; i *= 10) {
long long divider = i * 10;
count += (n / divider) * i + ((n % divider >= i) ? (n % divider - i + 1) : 0);
}
return count;
}
int main() {
int n = 13;
cout << countDigitOne(n) << endl;
return 0;
}function countDigitOne(n) {
let count = 0;
for (let i = 1; i <= n; i *= 10) {
const divider = i * 10;
count += Math.floor(n / divider) * i + Math.min(Math.max(n % divider - i + 1, 0), i);
}
return count;
}
const n = 13;
console.log(countDigitOne(n));#include <stdio.h>
int countDigitOne(int n) {
int count = 0;
for (long long i = 1; i <= n; i *= 10) {
long long divider = i * 10;
count += (n / divider) * i + ((n % divider >= i) ? (n % divider - i + 1) : 0);
}
return count;
}
int main() {
int n = 13;
printf("%d\n", countDigitOne(n));
return 0;
}using System;
class Program {
static int CountDigitOne(int n) {
int count = 0;
for (long i = 1; i <= n; i *= 10) {
long divider = i * 10;
count += (n / divider) * i + Math.Min(Math.Max(n % divider - i + 1, 0), i);
}
return count;
}
static void Main() {
int n = 13;
Console.WriteLine(CountDigitOne(n));
}
}In this Python solution, for each digit in n, the number of occurrences of '1' at that digit position is calculated and aggregated to provide the final count.
Time Complexity: O(log10(n)), since it checks each power of 10.
Space Complexity: O(1), as it uses constant extra space.
Approach 3: Digit DP
This problem essentially asks for the number of times the digit 1 appears in the given range [l, ..r]. The count is related to the number of digits and the value of each digit. We can use the concept of Digit DP to solve this problem. In Digit DP, the size of the number has little impact on the complexity.
For the range [l, ..r] problem, we generally convert it to the problem of [1, ..r] and then subtract the result of [1, ..l - 1], i.e.:
$
ans = sum_{i=1}^{r} ans_i - sum_{i=1}^{l-1} ans_i
However, for this problem, we only need to find the value for the range [1, ..r].
Here, we use memoized search to implement Digit DP. We search from the starting point downwards, and at the lowest level, we get the number of solutions. We then return the answers layer by layer upwards, and finally get the final answer from the starting point of the search.
The basic steps are as follows:
First, we convert the number n to a string s. Then we design a function dfs(i, cnt, limit), where:
- The digit i
represents the current position being searched, starting from the highest digit, i.e.,i = 0represents the highest digit. - The digit cnt
represents the current count of the digit1in the number. - The boolean limit
indicates whether the current number is restricted by the upper bound.
The function executes as follows:
If i exceeds the length of the number n, it means the search is over, directly return cnt. If limit is true, up is the i-th digit of the current number. Otherwise, up = 9. Next, we iterate j from 0 to up. For each j:
- If j
equals1, we incrementcntby one. - Recursively call dfs(i + 1, cnt, limit \land j = up)
.
The answer is dfs(0, 0, True).
The time complexity is O(m^2 times D), and the space complexity is O(m^2). Here, m is the length of the number n, and D = 10$.
Similar Problems:
Here is the translation of the similar problems into English:
function countDigitOne(n: number): number {
const s = n.toString();
const m = s.length;
const f: number[][] = Array.from({ length: m }, () => Array(m).fill(-1));
const dfs = (i: number, cnt: number, limit: boolean): number => {
if (i >= m) {
return cnt;
}
if (!limit && f[i][cnt] !== -1) {
return f[i][cnt];
}
const up = limit ? +s[i] : 9;
let ans = 0;
for (let j = 0; j <= up; ++j) {
ans += dfs(i + 1, cnt + (j === 1 ? 1 : 0), limit && j === up);
}
if (!limit) {
f[i][cnt] = ans;
}
return ans;
};
return dfs(0, 0, true);
}func countDigitOne(n int) int {
s := strconv.Itoa(n)
m := len(s)
f := make([][]int, m)
for i := range f {
f[i] = make([]int, m)
for j := range f[i] {
f[i][j] = -1
}
}
var dfs func(i, cnt int, limit bool) int
dfs = func(i, cnt int, limit bool) int {
if i >= m {
return cnt
}
if !limit && f[i][cnt] != -1 {
return f[i][cnt]
}
up := 9
if limit {
up = int(s[i] - '0')
}
ans := 0
for j := 0; j <= up; j++ {
t := 0
if j == 1 {
t = 1
}
ans += dfs(i+1, cnt+t, limit && j == up)
}
if !limit {
f[i][cnt] = ans
}
return ans
}
return dfs(0, 0, true)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * log10(n)), accounting for string conversion and counting. |
| Counting by Digit Position | Time Complexity: O(log10(n)), since it checks each power of 10. |
| Digit DP | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n log n) | O(1) | Useful for understanding the problem or when n is very small. |
| Counting by Digit Position | O(log n) | O(1) | Optimal solution for large inputs and the expected approach in coding interviews. |
Frequently asked questions
Is Number of Digit One easy or hard?
Number of Digit One is labeled Hard because the pattern is not obvious from the problem statement. The brute force approach is simple but inefficient, while the optimal O(log n) solution requires recognizing digit cycles and applying mathematical reasoning.
Number of Digit One Python/Java solution
Most implementations follow the same digit-position formula. Use a loop that multiplies a factor by 10 each iteration, derive higher/current/lower values from n, and update the result accordingly. The logic is identical across Python, Java, C++, and other languages.
How to solve Number of Digit One in O(log n)?
Iterate through digit positions using a factor variable (1, 10, 100...). For each position, compute the higher digits, the current digit, and the lower digits. Based on whether the current digit is 0, 1, or greater than 1, calculate how many ones appear in that position and accumulate the total.
What is the best approach for Number of Digit One?
The best approach counts contributions from each digit position independently. By analyzing the higher, current, and lower digits around a position (ones, tens, hundreds), you can compute how many times '1' appears at that position. This reduces the complexity to O(log n) time with O(1) space.
Is Number of Digit One asked at Google/Amazon/Meta?
Digit counting and range‑based math problems similar to Number of Digit One frequently appear in interviews at companies like Google, Amazon, and Meta. They test number pattern recognition, mathematical reasoning, and the ability to optimize beyond brute force solutions.
What data structure is used in Number of Digit One?
No complex data structure is required. The optimal solution relies on arithmetic operations and digit decomposition. Variables representing higher digits, the current digit, and lower digits are enough to compute the count.
What is the time complexity of Number of Digit One?
The optimal digit-position counting solution runs in O(log n) time because it processes each decimal digit once. Space complexity remains O(1) since only a few integer variables are required. A brute force approach that checks every number takes O(n log n).