Number of Digit One

hard math dp recursion

Problem

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Inputn = 13

Output6

Ones come from 1, 10, 11, 12, 13 → digits-with-1 count = 1+1+2+1+1 = 6. For each digit position with place value p (1, 10, 100, …), split n into high, cur, low parts and add the contribution at that place.

n (0..9999)

def count_digit_one(n):
    if n <= 0: return 0
    count, p = 0, 1
    while p <= n:
        high, cur, low = n // (p * 10), (n // p) % 10, n % p
        if cur == 0:   count += high * p
        elif cur == 1: count += high * p + low + 1
        else:          count += (high + 1) * p
        p *= 10
    return count

function countDigitOne(n) {
  if (n <= 0) return 0;
  let count = 0, p = 1;
  while (p <= n) {
    const high = Math.floor(n / (p * 10));
    const cur = Math.floor(n / p) % 10;
    const low = n % p;
    if (cur === 0) count += high * p;
    else if (cur === 1) count += high * p + low + 1;
    else count += (high + 1) * p;
    p *= 10;
  }
  return count;
}

class Solution {
    public int countDigitOne(int n) {
        if (n <= 0) return 0;
        long count = 0, p = 1;
        while (p <= n) {
            long high = n / (p * 10), cur = (n / p) % 10, low = n % p;
            if (cur == 0) count += high * p;
            else if (cur == 1) count += high * p + low + 1;
            else count += (high + 1) * p;
            p *= 10;
        }
        return (int) count;
    }
}

int countDigitOne(int n) {
    if (n <= 0) return 0;
    long long count = 0, p = 1;
    while (p <= n) {
        long long high = n / (p * 10), cur = (n / p) % 10, low = n % p;
        if (cur == 0) count += high * p;
        else if (cur == 1) count += high * p + low + 1;
        else count += (high + 1) * p;
        p *= 10;
    }
    return (int) count;
}

Explanation

Counting digit-1 occurrences by looping from 1 to n would be far too slow for large n. Instead we count, one digit position at a time, how many times a 1 appears at that place across all numbers up to n.

For each place value p (1, 10, 100, …) we split n into three parts: high = n // (p*10) (digits above the current place), cur = (n // p) % 10 (the current digit), and low = n % p (digits below it).

The count contributed at this place depends on cur: if cur == 0, add high * p; if cur == 1, add high * p + low + 1 (the partial range only goes up to low); if cur >= 2, add (high + 1) * p (a full extra block of 1s fits). Summing over all places gives the answer.

Example: n = 13. At the ones place (p=1): high=1, cur=3, low=0, so cur>=2 adds (1+1)*1 = 2. At the tens place (p=10): high=0, cur=1, low=3, so cur==1 adds 0 + 3 + 1 = 4. Total 2 + 4 = 6, matching the ones in 1,10,11,12,13.

We process only as many places as n has digits, so this runs in logarithmic time with constant space.

Time: O(log n) Space: O(1)