# [leetcode] 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.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Brute force solution o(n) in time, TLE.

```// brute force
class Solution {
public:
int countDigitOne(int n) {
int count = 0;
for(int i = 1; i <= n; i++){
int j = i;
while(j > 0){
if(j % 10 == 1){
count++;
break;
}else{
j = j / 10;
}
}
}
return count;
}
};```

A better solution.

Count the occurrence of 1 on every bit. Be aware of overflow.

```class Solution {
public:
int countDigitOne(int n) {
long pivot = 1;
int count = 0;
while(pivot <= (long)n * 10){
int left = n / (pivot * 10); // left part to pivot
int right = n % pivot; // right part to pivot
int digit = n / pivot % 10; // pivot digit
if(digit == 0) count += left * pivot;
else if(digit == 1) count += left * pivot + right + 1;
else count += left * pivot + pivot;
pivot = pivot * 10;
}
return count;
}
};```

Reference: https://leetcode.com/discuss/64962/java-python-one-pass-solution-easy-to-understand

The idea is to calculate occurrence of 1 on every digit. There are 3 scenarios, for example

``````if n = xyzdabc
``````

and we are considering the occurrence of one on thousand, it should be:

``````(1) xyz * 1000                     if d == 0
(2) xyz * 1000 + abc + 1           if d == 1
(3) xyz * 1000 + 1000              if d > 1
``````

iterate through all digits and sum them all will give the final answer

Java

``````public int countDigitOne(int n) {

if (n <= 0) return 0;
int q = n, x = 1, ans = 0;
do {
int digit = q % 10;
q /= 10;
ans += q * x;
if (digit == 1) ans += n % x + 1;
if (digit >  1) ans += x;
x *= 10;
} while (q > 0);
return ans;

}

// 40 / 40 test cases passed.
// Status: Accepted
// Runtime: 0 ms
``````

Python

``````def countDigitOne(self, n):
if n <= 0:
return 0
q, x, ans = n, 1, 0
while q > 0:
digit = q % 10
q /= 10
ans += q * x
if digit == 1:
ans += n % x + 1
elif digit > 1:
ans += x
x *= 10
return ans

# 40 / 40 test cases passed.
# Status: Accepted
# Runtime: 32 ms
# 97.59%``````

This site uses Akismet to reduce spam. Learn how your comment data is processed.