Problem Statement
You are given an integer n
. Count the total number of times the digit 1
appears in the decimal representation of all numbers from 1 to n
.
LeetCode
Constraints
0 <= n <= 10^9
Examples
Example 1:
Input: n = 13
Output: 6
Explanation:
The numbers from 1 to 13 are:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
Now count the number of '1's:
1 → 1 one
10 → 1 one
11 → 2 ones
12 → 1 one
13 → 1 one
Total = 6
Example 2:
Input: n = 100
Output: 21
Explanation:
The digit '1' appears:
Once in every ten numbers (in the units place)
Ten times in the tens place (10–19)
So you get:
1, 10–19 = 11 numbers
Plus 1 appears again at 21, 31, ..., 91 → 9 more
Total = 21
Example 3:
Input: n = 0
Output: 0
Different Approaches
1️⃣ Brute Force Approach
💡 Intuition:
We go through each number from 1 to n, and for each number, check how many times digit 1 appears in that number. We keep adding those counts together to get the total.
Code:
class Solution {
public:
// Helper function to count the number of digit '1' in a given number
int countOnesInNumber(int number) {
int count = 0;
// Iterate through each digit of the number
while (number != 0) {
// Check if the last digit is 1
if (number % 10 == 1) {
count++; // Increment count if digit is 1
}
number /= 10; // Remove the last digit
}
return count; // Return total count of digit '1' in the number
}
// Function to count total number of digit '1' from 1 to n
int countDigitOne(int n) {
int totalCount = 0;
// Loop through all numbers from 1 to n
for (int currentNumber = 1; currentNumber <= n; currentNumber++) {
// Add the count of '1's in the current number to the total
totalCount += countOnesInNumber(currentNumber);
}
return totalCount; // Return the final total count of digit '1'
}
};
🛠️ Complexity Analysis:
- Time Complexity:
O(n * d)
wheren
is the input andd
is the number of digits inn
(because for each number, we loop through its digits).(n *log n)
- Outer loop: runs
n
times - Inner work:
countOnesInNumber(i)
- Inside, we are diving the number by 10 each time.
- Each number has
log10(i)
digits.
- Outer loop: runs
- Total Time:
O(n log n)
log 1 + log 2 + log 3 + … + log n
~log(n!)
~n log n
- Hence, the total time is:
O(n log n)
- Space Complexity: O(1) – no extra space used apart from variables.
2️⃣ Digit DP
Code:
class Solution {
public:
// dp[position][tight][count_of_ones]
int dp[11][2][11]; // Max 10 digits, tight = 0 or 1, max 10 ones (since at most 10 digits)
// Recursive function to solve digit DP
int solve(int index, int tight, int count, string& numStr) {
// Base Case:
// If we've processed all digits, return the number of 1s counted so far
if (index >= numStr.size()) {
return count;
}
// If this state is already solved, return the cached result
if (dp[index][tight][count] != -1) {
return dp[index][tight][count];
}
// Determine the digit limit at the current position
// If tight is true, we must not go above the current digit in numStr
// If tight is false, we can go freely up to 9
int limit = tight ? (numStr[index] - '0') : 9;
int ans = 0;
// Try placing every digit from 0 to 'limit' at the current position
for (int digit = 0; digit <= limit; digit++) {
// If we choose digit == limit and tight is true, newTight remains true
// Otherwise, we are no longer tight with the original number
bool newTight = tight && (digit == limit);
// If current digit is 1, increase the count
int newCount = count + (digit == 1 ? 1 : 0);
// Recur for the next position with updated count and tightness
ans += solve(index + 1, newTight, newCount, numStr);
}
// Store the result in dp and return it
return dp[index][tight][count] = ans;
}
int countDigitOne(int n) {
// Convert the number to a string so we can access digits by position
string numStr = to_string(n);
// Initialize the memoization table with -1 (uncomputed state)
memset(dp, -1, sizeof(dp));
// Start from index 0, tight = 1 (we are limited by numStr), count = 0
return solve(0, 1, 0, numStr);
}
};
Complexity Analysis:
- Time Complexity:
O(1)
- index: can be from 0 to 10 = 11 values
- tight: 0 0r 1 = 2 values
- count: from 0 to 10 = 11 values
- So total number of DP states:
11 * 2 * 11
=242
- And for each state, we are looping through at most 10 digits
(0 - 9)
, so total operations are:O(242 * 10) = O(2420) ~ O(1)
= constant time
- Space Complexity:
O(1)
- Small DP table + a little bit of stack space for recursion