Number of Digit One

Description

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(javascript)

/**
 * @param {number} n
 * @return {number}
 */
const 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)
}