233. 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 1:

Input: n = 13
Output: 6

Example 2:

Input: n = 0
Output: 0

 

Constraints:

• 0 <= n <= 109

 

Solutions

Solution: Recursion

• Time complexity: O(logn)
• Space complexity: O(logn)

 

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
const countDigitOne = function (n) {
  const sumCount = num => {
    if (num < 1) return 0;
    let first = num;
    let digits = 1;
    let rest = 0;

    while (first >= 10) {
      first = Math.floor(first / 10);
      digits *= 10;
    }
    rest = num % digits;

    const result = first * sumCount(digits - 1) + sumCount(rest);

    return result + (first === 1 ? rest + 1 : digits);
  };

  return sumCount(n);
};