# Number of Digit One
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-digit-one)
Canonical: https://scaleengineer.com/dsa/problems/number-of-digit-one
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [Google](https://scaleengineer.com/companies/google)
---
## 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 <= 109`

# Approaches
## Brute Force Approach
Iterate through all numbers from 1 to n and count the number of 1's in each number.
**Time:** O(n * log n) - where n is the input number and log n is for converting each number to string and counting 1's · **Space:** O(log n) - space needed to store the string representation of numbers
**Pros:** Simple to understand and implement; Works for small inputs
**Cons:** Very inefficient for large numbers; Time complexity is high; Not suitable for the given constraints
### Explanation
For each number from 1 to n:
1. Convert the number to string
2. Count the occurrences of '1' in the string
3. Add the count to total

```java
public int countDigitOne(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        String num = String.valueOf(i);
        for (char c : num.toCharArray()) {
            if (c == '1') {
                count++;
            }
        }
    }
    return count;
}
```
### Algorithm
1. Initialize count = 0
2. Loop from i = 1 to n
3. Convert i to string
4. Count '1's in the string
5. Add count to total
6. Return total count

## Mathematical Pattern Approach
Use mathematical pattern to count number of 1's by analyzing each digit position and calculating contribution of 1's at each position.
**Time:** O(log n) - we only need to check each digit position · **Space:** O(1) - only uses a constant amount of extra space
**Pros:** Very efficient solution; Works for all input ranges; Handles large numbers effectively
**Cons:** More complex to understand; Requires understanding of mathematical pattern; Code might be less intuitive
### Explanation
For each digit position:
1. Calculate the contribution of 1's before current digit
2. Calculate the contribution of 1's at current digit
3. Calculate the contribution of 1's after current digit

```java
public int countDigitOne(int n) {
    int count = 0;
    for (long i = 1; i <= n; i *= 10) {
        long divider = i * 10;
        count += (n / divider) * i + Math.min(Math.max(n % divider - i + 1, 0L), i);
    }
    return count;
}
```

For each position i:
- n/divider gives the number of complete groups
- Each complete group contributes i ones
- The remainder (n % divider) determines if there are additional ones
### Algorithm
1. Initialize count = 0
2. For each digit position (i = 1, 10, 100, ...)
3. Calculate complete groups contribution
4. Calculate partial group contribution
5. Add to total count
6. Return final count

# Solutions
### CSharp

```csharp
public class Solution { public int CountDigitOne ( int n ) { if ( n <= 0 ) return 0 ; if ( n < 10 ) return 1 ; return CountDigitOne ( n / 10 - 1 ) * 10 + n / 10 + CountDigitOneOfN ( n / 10 ) * ( n % 10 + 1 ) + ( n % 10 >= 1 ? 1 : 0 ); } private int CountDigitOneOfN ( int n ) { var count = 0 ; while ( n > 0 ) { if ( n % 10 == 1 ) ++ count ; n /= 10 ; } return count ; } }
```

### Java

```java
class Solution { private int [] a = new int [ 12 ]; private int [][] dp = new int [ 12 ][ 12 ]; public int countDigitOne ( int n ) { int len = 0 ; while ( n > 0 ) { a [++ len ] = n % 10 ; n /= 10 ; } for ( var e : dp ) { Arrays . fill ( e , - 1 ); } return dfs ( len , 0 , true ); } private int dfs ( int pos , int cnt , boolean limit ) { if ( pos <= 0 ) { return cnt ; } if (! limit && dp [ pos ][ cnt ] != - 1 ) { return dp [ pos ][ cnt ]; } int up = limit ? a [ pos ] : 9 ; int ans = 0 ; for ( int i = 0 ; i <= up ; ++ i ) { ans += dfs ( pos - 1 , cnt + ( i == 1 ? 1 : 0 ), limit && i == up ); } if (! limit ) { dp [ pos ][ cnt ] = ans ; } return ans ; } }
```

### CPP

```cpp
class Solution {
public:
  int a[12];
  int dp[12][12];
  int countDigitOne(int n) {
    int len = 0;
    while (n) {
      a[++len] = n % 10;
      n /= 10;
    }
    memset(dp, -1, sizeof dp);
    return dfs(len, 0, true);
  }
  int dfs(int pos, int cnt, bool limit) {
    if (pos <= 0) {
      return cnt;
    }
    if (!limit && dp[pos][cnt] != -1) {
      return dp[pos][cnt];
    }
    int ans = 0;
    int up = limit ? a[pos] : 9;
    for (int i = 0; i <= up; ++i) {
      ans += dfs(pos - 1, cnt + (i == 1), limit && i == up);
    }
    if (!limit) {
      dp[pos][cnt] = ans;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countDigitOne(self, n: int) -> int: @ cache def dfs(pos, cnt, limit): if pos <= 0: return cnt up = a[pos] if limit else 9 ans = 0 for i in range(up + 1): ans += dfs(pos - 1, cnt + (i == 1), limit and i == up) return ans a = [0] * 12 l = 1 while n: a[l] = n % 10 n //= 10 l += 1 return dfs(l, 0, True)

```