Problem
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 <= 10^9
Solution
/**
* @param {number} n
* @return {number}
*/
var countDigitOne = function(n) {
const memo = {}
const aux = (number) => {
if (memo[number] !== undefined) {
return memo[number]
}
if (number <= 0) {
return 0
}
const str = number.toString()
const first = parseInt(str[0], 10)
const base = Math.pow(10, str.length - 1)
const reminder = number - first * base
if (first === 1) {
memo[number] = aux(base - 1) + reminder + 1 + aux(reminder)
} else {
memo[number] = first * aux(base - 1) + base + aux(reminder)
}
return memo[number]
}
return aux(n)
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).