# 233. Number of Digit One
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
Example:
Input: 13
Output: 6
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
# Solution
Approach 1: (Time Limit Exceeded) Brute force.
Approach 2: Solve it mathematically.
# Code (Python)
Approach 1:
Approach 2:
# Code (C++)
Approach 1:
// Brute force [Time Limit Exceeded]
class Solution {
public:
int countDigitOne(int n) {
int res = 0;
for (int i = 1; i <= n; ++i)
{
string str = to_string(i);
res += count(str.begin(), str.end(), '1');
}
return res;
}
};
Approach 2:
// Solve it mathematically.
class Solution {
public:
int countDigitOne(int n) {
long base = 1;
int count = 0;
while (n / base > 0)
{
int high = n / base / 10;
int low = n % base;
int curr = n / base - (high * 10);
if (curr == 1)
count += 1 * (low + 1) + high * base;
else if (curr == 0)
count += 0 * (low + 1) + high * base;
else // count > 1
count += (high + 1) * base;
base *= 10;
}
return count;
}
};
// Solve it mathematically.
class Solution {
public:
int countDigitOne(int n) {
long base = 1;
int count = 0;
int high = n / 10;
int low = 0;
int curr = n % 10;
while (low < n)
{
if (curr == 1)
count += 1 * (low + 1) + high * base;
else if (curr == 0)
count += 0 * (low + 1) + high * base;
else // count > 1
count += (high + 1) * base;
low += curr * base;
curr = high % 10;
high /= 10;
base *= 10;
}
return count;
}
};