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 <= 109In 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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(log10(n)), as it iterates digit by digit.
Space Complexity: O(1), as it uses a fixed amount of space.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * log10(n)), as it checks each digit of each number from 1 to n. |
| Counting by Digit Position | Time Complexity: O(log10(n)), as it iterates digit by digit. |
Plus One - Leetcode 66 - Python • NeetCode • 62,651 views views
Watch 9 more video solutions →Practice Number of Digit One with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor