Number of Digit One

Problem Statement

You are given an integer n. Count the total number of times the digit 1 appears in the decimal representation of all numbers from 1 to n.

LeetCode

• https://leetcode.com/problems/number-of-digit-one/

Constraints

0 <= n <= 10^9

Examples

Example 1:

Input: n = 13
Output: 6

Explanation:
The numbers from 1 to 13 are:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
Now count the number of '1's:
1 → 1 one
10 → 1 one
11 → 2 ones
12 → 1 one
13 → 1 one
Total = 6

Example 2:

Input: n = 100
Output: 21

Explanation:
The digit '1' appears:
Once in every ten numbers (in the units place)
Ten times in the tens place (10–19)
So you get:
1, 10–19 = 11 numbers
Plus 1 appears again at 21, 31, ..., 91 → 9 more
Total = 21

Example 3:

Input: n = 0
Output: 0

Different Approaches

1️⃣ Brute Force Approach

💡 Intuition:

We go through each number from 1 to n, and for each number, check how many times digit 1 appears in that number. We keep adding those counts together to get the total.

Code:

class Solution {
public:
    // Helper function to count the number of digit '1' in a given number
    int countOnesInNumber(int number) {
        int count = 0;
        
        // Iterate through each digit of the number
        while (number != 0) {
            // Check if the last digit is 1
            if (number % 10 == 1) {
                count++; // Increment count if digit is 1
            }
            number /= 10; // Remove the last digit
        }
        
        return count; // Return total count of digit '1' in the number
    }

    // Function to count total number of digit '1' from 1 to n
    int countDigitOne(int n) {
        int totalCount = 0;

        // Loop through all numbers from 1 to n
        for (int currentNumber = 1; currentNumber <= n; currentNumber++) {
            // Add the count of '1's in the current number to the total
            totalCount += countOnesInNumber(currentNumber);
        }

        return totalCount; // Return the final total count of digit '1'
    }
};

🛠️ Complexity Analysis:

• Time Complexity:O(n * d) where n is the input and d is the number of digits in n (because for each number, we loop through its digits).
  • (n *log n)
    • Outer loop: runs n times
    • Inner work: countOnesInNumber(i)
      • Inside, we are diving the number by 10 each time.
      • Each number has log10(i) digits.
  • Total Time: O(n log n)
    • log 1 + log 2 + log 3 + … + log n ~ log(n!) ~ n log n
    • Hence, the total time is: O(n log n)
• Space Complexity: O(1) – no extra space used apart from variables.

2️⃣ Digit DP

Code:

class Solution {
public:
    // dp[position][tight][count_of_ones]
    int dp[11][2][11]; // Max 10 digits, tight = 0 or 1, max 10 ones (since at most 10 digits)

    // Recursive function to solve digit DP
    int solve(int index, int tight, int count, string& numStr) {
        // Base Case:
        // If we've processed all digits, return the number of 1s counted so far
        if (index >= numStr.size()) {
            return count;
        }

        // If this state is already solved, return the cached result
        if (dp[index][tight][count] != -1) {
            return dp[index][tight][count];
        }

        // Determine the digit limit at the current position
        // If tight is true, we must not go above the current digit in numStr
        // If tight is false, we can go freely up to 9
        int limit = tight ? (numStr[index] - '0') : 9;

        int ans = 0;

        // Try placing every digit from 0 to 'limit' at the current position
        for (int digit = 0; digit <= limit; digit++) {
            // If we choose digit == limit and tight is true, newTight remains true
            // Otherwise, we are no longer tight with the original number
            bool newTight = tight && (digit == limit);

            // If current digit is 1, increase the count
            int newCount = count + (digit == 1 ? 1 : 0);

            // Recur for the next position with updated count and tightness
            ans += solve(index + 1, newTight, newCount, numStr);
        }

        // Store the result in dp and return it
        return dp[index][tight][count] = ans;
    }

    int countDigitOne(int n) {
        // Convert the number to a string so we can access digits by position
        string numStr = to_string(n);

        // Initialize the memoization table with -1 (uncomputed state)
        memset(dp, -1, sizeof(dp));

        // Start from index 0, tight = 1 (we are limited by numStr), count = 0
        return solve(0, 1, 0, numStr);
    }
};

Complexity Analysis:

• Time Complexity:O(1)
  • index: can be from 0 to 10 = 11 values
  • tight: 0 0r 1 = 2 values
  • count: from 0 to 10 = 11 values
  • So total number of DP states: 11 * 2 * 11 = 242
  • And for each state, we are looping through at most 10 digits (0 - 9), so total operations are:
    • O(242 * 10) = O(2420) ~ O(1) = constant time
• Space Complexity:O(1)
  • Small DP table + a little bit of stack space for recursion