Skip to main content
Talentd

Number of Digit One - Solution & Explanation

HardMathDynamic ProgrammingRecursion24 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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.

The code iterates from 1 to n and for each number, it counts the number of the digit 1 by repeatedly dividing the number by 10 and checking the remainder. It increments count each time a 1 is found.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * log10(n)), as it checks each digit of each number from 1 to n.
Space Complexity: O(1), as it uses a fixed amount of space.

Try this approach in the editor →

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.

The C code iterates over each digit position and calculates how often a 1 would appear at that position using arithmetic based on the surrounding digits. The core idea is to count 1s in each digit position separately.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log10(n)), as it iterates digit by digit.
Space Complexity: O(1), as it uses a fixed amount of space.

Try this approach in the editor →

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 = 0 represents the highest digit.
  • The digit cnt represents the current count of the digit 1 in 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 equals 1, we increment cnt by 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:

Code

PythonJavaC++GoTypeScriptC#

Python

Java

C++

Go

TypeScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n * log10(n)), as it checks each digit of each number from 1 to n.
Space Complexity: O(1), as it uses a fixed amount of space.

Counting by Digit Position

Time Complexity: O(log10(n)), as it iterates digit by digit.
Space Complexity: O(1), as it uses a fixed amount of space.

Digit DP—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n log n)O(1)Useful for understanding the problem or when n is very small.
Counting by Digit PositionO(log n)O(1)Optimal solution for large inputs and the expected approach in coding interviews.

Video Solution

Leetcode 233(Hard) Number of Digit One: Simple C++ Solution • Shivam Patel • 11,327 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Number of Digit One with our built-in code editor and test cases.

Practice on FleetCode
Previous

Digit Count in Range

Next

Factorial Trailing Zeroes