Skip to main content

Math Basics

Count the Occurrences of Digit '1' in All Numbers from 1 to n Solution In C++/Java/Python/JS

Count the occurrences of digit '1' in all numbers from 1 to n
Count the occurrences of digit '1' in all numbers from 1 to n

Problem Description:

Given an integer n, count the occurrences of the digit '1' in all numbers from 1 to n.

Examples:

Input: n = 13
Output: 6
Explanation: The numbers containing '1' are 1, 10, 11, 12, 13. The total count is 6.

Example 2:

Input: n = 100
Output: 21

Constraints:

  • 1 <= n <= 109

Brute Force Approach

Intuition:

After getting a clear view of the problem statement, what is the first thing that comes to mind?

We know that we need the count of occurrences of ones from 1 to n.

Count the occurrences of digit '1' in all numbers from 1 to n solution

The most straightforward way to solve this problem is to check each number from 1 to n and count how many times the digit '1' appears in each of them.

How do we count occurrences of '1' in a number?

To do this, we can follow the following approach.

  • Convert the number to a string.
  • Check each character and count how many '1's appear.

Count the occurrences of digit '1' in all numbers from 1 to n Example

Input: n=11
Ouptut: 4
Explanation: numbers containing '1's are 1, 10, 11. total '1's count = 4.

Initialization:

  • count = 0

Loop Execution:

We iterate over all numbers from 1 to n, converting each number to a string and counting occurrences of '1'.

Step-by-step Execution

Iteration 1: i = 1

  • Convert 1 to string → "1"
  • Count occurrences of '1' → 1
  • count = 0 + 1 = 1

Iteration 2: i = 2

  • Convert 2 to string → `2"
  • Count occurrences of '1' → 0
  • count = 1 + 0 = 1

Iteration 3: i = 3

  • Convert 3 to string → "3"
  • Count occurrences of '1' → 0
  • count = 1 + 0 = 1

Iteration 4: i = 4

  • Convert 4 to string → "4"
  • Count occurrences of '1' → 0
  • count = 1 + 0 = 1

Iteration 5: i = 5

  • Convert 5 to string → "5"
  • Count occurrences of '1' → 0
  • count = 1 + 0 = 1

Iteration 6: i = 6

  • Convert 6 to string → "6"
  • Count occurrences of '1' → 0
  • count = 1 + 0 = 1

Iteration 7: i = 7

  • Convert 7 to string → "7"
  • Count occurrences of '1' → 0
  • count = 1 + 0 = 1

Iteration 8: i = 8

  • Convert 8 to string → "8"
  • Count occurrences of '1' → 0
  • count = 1 + 0 = 1

Iteration 9: i = 9

  • Convert 9 to string → "9"
  • Count occurrences of '1' → 0
  • count = 1 + 0 = 1

Iteration 10: i = 10

  • Convert 10 to string → "10"
  • Count occurrences of '1' → 1
  • count = 1 + 1 = 2

Iteration 11: i = 11

  • Convert 11 to string → "11"
  • Count occurrences of '1' → 2
  • count = 2 + 2 = 4

Final Output

count = 4, so the program prints: 4

Steps to write code

Step 1: Initialize a variable count = 0.

Step 2: Loop through numbers from 1 to n.

Step 3: Convert each number to a string.

Step 4: Count how many times '1' appears and add it to count.

Step 5: Return count.

Count the occurrences of digit '1' in all numbers from 1 to n solution
Count the occurrences of digit '1' in all numbers from 1 to n solution in C++ 
int countDigitOne(int n) {
    // Initialize a counter to keep track of occurrences of '1'
    int count = 0;
    
    // Iterate through every number from 1 to n
    for (int i = 1; i <= n; i++) {
        // Convert the current number to a string
        string num = to_string(i);
        
        // Count the occurrences of '1' in the string representation of the number
        for(auto c : num) {
			if(c == '1'){
				count++;
			}
		}
    }
    
    // Return the final count of '1' occurrences
    return count;
}

Count the occurrences of digit '1' in all numbers from 1 to n solution in Java 
class Solution {
    public static int countDigitOne(int n) {
        // Initialize a counter to keep track of occurrences of '1'
        int count = 0;

        // Iterate through every number from 1 to n
        for (int i = 1; i <= n; i++) {
            // Convert the current number to a string
            String num = Integer.toString(i);
            
            // Count occurrences of '1' in the string representation of the number
            count += num.chars().filter(ch -> ch == '1').count();
        }

        // Return the final count of '1' occurrences
        return count;
    }
}

Count the occurrences of digit '1' in all numbers from 1 to n solution in Python 
def count_digit_one(n):
    # Initialize a counter to keep track of occurrences of '1'
    count = 0
    
    # Iterate through every number from 1 to n
    for i in range(1, n + 1):
        # Convert the current number to a string
        num = str(i)
        
        # Count occurrences of '1' in the string representation of the number
        count += num.count('1')
    
    # Return the final count of '1' occurrences
    return count

Count the occurrences of digit '1' in all numbers from 1 to n solution in Javascript 
// Function to count occurrences of digit '1' from 1 to n
var countDigitOne = function(n) {
    // Initialize a counter to keep track of occurrences of '1'
    let count = 0;

    // Iterate through every number from 1 to n
    for (let i = 1; i <= n; i++) {
        // Convert the current number to a string
        let num = i.toString();

        // Count occurrences of '1' in the string representation of the number
        count += num.split('1').length - 1;
    }

    // Return the final count of '1' occurrences
    return count;
}

Count the occurrences of digit '1' in all numbers from 1 to n Complexity Analysis

Time Complexity: O(n×d)

  • Looping through numbers from 1 to n results to the complexity of O(n)
  • Converting a number to a string takes O(d) time, where d is the number of digits in the number.
  • Counting '1's in the string takes O(d) time.
  • Hence time complexity of the brute force approach is O(n×d).
  • In the worst case, d is around 10 (since n ≤ 109), leading to approximately O(10×n), which is inefficient for large n.

Space Complexity: O(1)

Auxiliary Space Complexity

It refers to the space used to solve the problem excluding input space.

  • The function uses a few integer variables (count, i, num), which take constant space: O(1).
  • Each number is converted to a string (to_string(i)), which requires O(d) space per number (where d is the number of digits in i).
  • Since the conversion happens within the loop and is discarded after each iteration, it does not accumulate across iterations.
  • Thus, the overall auxiliary space remains O(1).

Total Space Complexity

It accounts both auxiliary as well as input space complexity.

  • Auxiliary space complexity is O(1).
  • Input is a single integer n hence, O(1).
  • The total space complexity is O(1), as we are not using any data structures that scale with n.

Is the brute force approach efficient?.

Since the constraint on n is up to 10⁹, iterating through all numbers from 1 to n in the brute force approach is not feasible. This is because the time complexity of brute force is O(n×10), which becomes extremely slow for large n.

To solve this problem efficiently, we need to think of a better approach that avoids checking every number individually.

Optimal Approach

Intuition:

Instead of iterating through every number from 1 to n and checking for the occurrence of 1 (which is inefficient), we analyze each digit position separately.

Key Idea

For each digit place (ones, tens, hundreds, etc.), we count how many times the digit 1 appears at that place across all numbers from 1 to n.

  • Ones place (1, 11, 21, 31, ..., 311)
  • Tens place (10-19, 110-119, 210-219, ...)
  • Hundreds place (100-199)

Count the occurrences of digit '1' in all numbers from 1 to n Algorithm

To count how many times '1' occurs at any digit position, we define three values. higher, current, lower.

  • higher stores the digits to the left of the current digit place.
  • current stores the value of the current digit for which we are counting occurrences of '1'.
  • lower stores the digits which are right of the current place.

To compute higher, we need only those digits that are left of the current digit; for this, we can use powers of 10

For example, if n = 2345 and we need a 'higher' for the, ones place. To get it, we will divide n by 10, which will give us 234. Similarly, for the hundreds' place we divide n by 100 and receive 23, only those digits that are left of 4 (hundreds place).

To compute current, we can divide 10 such that the current element remains and all those left of the current disappear. To do this, we divide n by 1 for the ones place and 10 for the hundreds place. After that, we simply take the modulo 10 to get the last digit (which is current).

For example, if n = 2345, If we need to extract 5, we can divide n by 1, which gives n and then take the modulo 10, which gives 5. To extract 3, we divide n by 100 to remove 45 (left of 3) and get 23. After this, taking modulo 10 will give the required last digit 3.

To compute lower, we can make use of modulo 10x. If we compute n%10, then we will receive a number with the last digit. If we compute n%100, then we receive a number with the last 2 digits.

For example, if n = 2345, if we need to extract 'lower' of 3, that means we want 45, so we will take modulo 100 because we need the last 2 digits. This means 2345%100 = 45. Do you see the pattern...

To summarize this:

We can build a formula to get higher, lower and current.

  1. higher = n / (factor * 10): Digits to the left of the current place.
  2. current = (n / factor) % 10: The digit at the current place.
  3. lower = n % factor: Digits to the right of the current place.

Here factor is a multiple of 10 based on the digit we are currently processing.

  • ones → factor = 1
  • tens → factor = 10
  • hundreds → factor = 100.. so on.

Now that we know how to compute higher, current and lower. Let's see how we will use these values to calculate the total number of 1's, which we will add to our answer.

To understand this, we need to look at 3 cases:-

Case 1: When the Current Digit is 0

Imagine you are looking at a particular place value, and the digit there is 0. What does this mean? It means that '1' can only come from numbers formed by the higher part of the number.

For example, in 2045, when looking at the hundreds place (0 in this case), we realize that '1' only appears in previous full cycles of hundreds (100-199, 1100-1199, etc.). Since 0 cannot contribute to forming new numbers with '1', the count of ones at this position is determined solely by the higher numbers.

The formula for this case is:

count = higher×factor

where factor is the place value (1 for ones, 10 for tens, 100 for hundreds, etc.).

Case 2: When the Current Digit is 1

Now, what if the current digit is exactly 1? This changes things!

Not only do we count occurrences of '1' from the higher part (as in Case 1), but we also get additional numbers from the lower part.

For example, in 2145, if we are analyzing the hundreds place, the current digit is 1. Here’s what happens:

  • The higher part (2) means there were full sets of 100-199 and 1100-1199, contributing 2 × 100 = 200 occurrences of '1'.
  • The lower part (45) means that in the current range (2100-2145), all numbers from 2100 to 2145 contain '1' in the hundreds place. This adds 45 + 1 = 46 more occurrences.

So, when the current digit is 1, the formula becomes:

count = higher×factor+(lower+1)

This extra lower + 1 ensures we count the additional numbers from the current range.

Case 3: When the Current Digit is Greater than 1

What happens when the current digit is something greater than 1?

This is the best case because now we know that a complete block of numbers containing '1' is already fully present!

For example, in 3155, if we check the tens place (5 in this case), we see:

  • The higher part (31) means that all numbers in 10-19, 100-119, etc., have contributed fully.
  • Since 5 is greater than 1, this means that an extra full set of 100 numbers (3110-3119) will contribute completely, so we add one more block of factor.

The formula for this case is:

count = (higher+1)×factor

This extra +1 in higher accounts for the additional full block of numbers contributing to the count.

Let's understand this with an example

For example, let's analyze how often 1 appears in each digit place for n = 315, breaking it down digit-by-digit.

Counting '1's in the Ones Place (factor = 1)

We check how many times 1 appears in the ones place (i.e., the last digit).

  • Breakdown:
    • higher = 315 / 10 = 32 (digits left of the ones place)
    • current = (315 / 1) % 10 = 5 (current digit at ones place)
    • lower = 315 % 1 = 0 (digits right of the ones place)
  • How many numbers have '1' in the one'sones place?
    • Every complete set of 0-9 contributes one 1.
    • We have 32 full cycles of 0-9, so there are 32 occurrences of 1 in the ones place. (0-9, 10-19, 20-29...320-325).

Total count from one's place: (31 + 1) × 1 = 32.

This can be formulated by the expression: [(higher + 1) × factor]

Counting 1s in the Tens Place (factor = 10)

We check how many times 1 appears in the tens place (i.e., second-last digit).

  • Breakdown:
    • higher = 315 / (10 * 10) = 3
    • current = (315 / 10) % 10 = 2
    • lower = 315 % 10 = 5
  • How many numbers have 1 in tens place?
    • There are 3 complete sets of 00-99 contributing 10 occurrences each (10-19, 110-119, 210-219).
    • Since the current digit is exactly 1, we count the numbers from 310 to 315 in the last incomplete block.

Count from the tens place: (3×10)+(5+1)=30+6=36

This can be formulated by the expression: [(higher × factor) + lower + 1]

Counting 1s in the Hundreds Place (factor = 100)

We check how many times 1 appears in the hundreds place (i.e., third-last digit).

  • Breakdown:
    • higher = 315 / (100 * 10) = 0
    • current = (315 / 100) % 10 = 3
    • lower = 315 % 100 = 25
  • How many numbers have 1 in the hundreds place?
    • Since current > 1, we count all numbers in 000-199, meaning:
    • (higher + 1) * factor = (0 + 1) * 100 = 100.

Total count from hundreds place: 1 × 100 = 100

Final Result

Summing all contributions:

  • One's place: 32
  • Tens place: 36
  • Hundreds place: 100
  • Total: 32 + 36 + 100 = 168

After understanding the formulas we can summarize the optimal solution with the following.

If count is the total number of occurrences of '1's in all numbers from 1 to n.

Formula for Each Digit Place

For any digit position (factor = 1, 10, 100, ...):

  1. If current == 0:
    • count += higher × factor
  2. If current == 1:
    • count += higher × factor + lower + 1
  3. If current > 1:
    • count += (higher + 1) × factor
0:00
/1:14

Illustration of How Optimal Approach Works.

Count the occurrences of digit '1' in all numbers from 1 to n Example

Input: n=11
Ouptut: 4
Explanation: numbers containing '1's are 1, 10, 11. total '1's count = 4.

Initialization

  • count = 0
  • factor = 1

Iteration 1 (Checking the Ones Place)

  • higher = 11 / (1 * 10) = 1
  • current = (11 / 1) % 10 = 1
  • lower = 11 % 1 = 0

Condition Check

  • Since current == 1, we use:
    • count+=higher×factor+lower+1 → 1×1+0+1=2
  • Updated count = 2
  • Update factor = 1 × 10 = 10

Iteration 2 (Checking the Tens Place)

  • higher = 11 / (10 * 10) = 0
  • current = (11 / 10) % 10 = 1
  • lower = 11 % 10 = 1

Condition Check

  • Since current == 1, we use:
    • count += higher×factor+lower+1 → 0×10+1+1=2
  • Updated count = 4
  • Update factor = 10 × 10 = 100

Iteration 3 (Checking the Hundreds Place)

  • n / factor = 11 / 100 = 0 (loop terminates)

Final Output

Total count of digit 1 from 1 to 11 = 4

Steps to write code

Step 1: Initialize count to 0 and factor to 1.

Step 2: Run a while loop till n / factore is greater than 0.

Step 3: Compute higher = n / (factor * 10), current = (n / factor) % 10, and lower = n % factor.

    • If current == 0, count is higher * factor.
    • If current == 1, count is higher * factor + lower + 1.
    • If current > 1, count is (higher + 1) * factor.

Step 4: Move to the next digit place by multiplying factor by 10.

Step 5: Return count.

Count the occurrences of digit '1' in all numbers from 1 to n solution
C++ 
class Solution  {
public:
    // Function to count occurrences of digit '1' from 1 to n
    int countDigitOne(int n) {
        // Initialize counter to keep track of occurrences of '1'
        int count = 0;

        // Factor represents the current place value (ones, tens, hundreds, etc.)
        int factor = 1;

        // Loop until we process all digit places
        while (n / factor > 0) {
            // Extract higher part (left side of current digit)
            int higher = n / (factor * 10);

            // Extract current digit
            int current = (n / factor) % 10;

            // Extract lower part (right side of current digit)
            int lower = n % factor;

            // Apply logic based on the value of the current digit
            if (current == 0) 
                count += higher * factor;  // No extra '1's added
            else if (current == 1) 
                count += higher * factor + lower + 1;  // Include the numbers formed by lower part
            else 
                count += (higher + 1) * factor;  // Add extra full block

            // Move to the next digit place (ones → tens → hundreds)
            factor *= 10;
        }

        // Return the total count of '1' occurrences
        return count;
    }
};

Count the occurrences of digit '1' in all numbers from 1 to n solution in java 
class Solution {
    // Function to count occurrences of digit '1' from 1 to n
    public static int countDigitOne(int n) {
        // Initialize counter to keep track of occurrences of '1'
        int count = 0;

        // Factor represents the current place value (ones, tens, hundreds, etc.)
        int factor = 1;

        // Loop until we process all digit places
        while (n / factor > 0) {
            // Extract higher part (left side of current digit)
            int higher = n / (factor * 10);

            // Extract current digit
            int current = (n / factor) % 10;

            // Extract lower part (right side of current digit)
            int lower = n % factor;

            // Apply logic based on the value of the current digit
            if (current == 0) 
                count += higher * factor;  // No extra '1's added
            else if (current == 1) 
                count += higher * factor + lower + 1;  // Include the numbers formed by lower part
            else 
                count += (higher + 1) * factor;  // Add extra full block

            // Move to the next digit place (ones → tens → hundreds)
            factor *= 10;
        }

        // Return the total count of '1' occurrences
        return count;
    }
}

Count the occurrences of digit '1' in all numbers from 1 to n solution in Python 
def count_digit_one(n):
    # Initialize counter to keep track of occurrences of '1'
    count = 0

    # Factor represents the current place value (ones, tens, hundreds, etc.)
    factor = 1

    # Loop until we process all digit places
    while n // factor > 0:
        # Extract higher part (left side of current digit)
        higher = n // (factor * 10)

        # Extract current digit
        current = (n // factor) % 10

        # Extract lower part (right side of current digit)
        lower = n % factor

        # Apply logic based on the value of the current digit
        if current == 0:
            count += higher * factor  # No extra '1's added
        elif current == 1:
            count += higher * factor + lower + 1  # Include the numbers formed by lower part
        else:
            count += (higher + 1) * factor  # Add extra full block

        # Move to the next digit place (ones → tens → hundreds)
        factor *= 10

    # Return the total count of '1' occurrences
    return count

Count the occurrences of digit '1' in all numbers from 1 to n solution in Javascript 
var countDigitOne = function(n) {
    // Initialize counter to keep track of occurrences of '1'
    let count = 0;

    // Factor represents the current place value (ones, tens, hundreds, etc.)
    let factor = 1;

    // Loop until we process all digit places
    while (Math.floor(n / factor) > 0) {
        // Extract higher part (left side of current digit)
        let higher = Math.floor(n / (factor * 10));

        // Extract current digit
        let current = Math.floor(n / factor) % 10;

        // Extract lower part (right side of current digit)
        let lower = n % factor;

        // Apply logic based on the value of the current digit
        if (current === 0) 
            count += higher * factor;  // No extra '1's added
        else if (current === 1) 
            count += higher * factor + lower + 1;  // Include the numbers formed by lower part
        else 
            count += (higher + 1) * factor;  // Add extra full block

        // Move to the next digit place (ones → tens → hundreds)
        factor *= 10;
    }

    // Return the total count of '1' occurrences
    return count;
}

Count the occurrences of digit '1' in all numbers from 1 to n Complexity Analysis

Time Complexity: O(logn)

Each digit of n is processed once. Since n has at most log10(n) digits, the loop runs O(log n) times.

Each iteration performs constant-time operations, leading to an overall complexity of O(log n).

Space Complexity: O(1)

Auxiliary Space Complexity

It refers to the space used to solve the problem excluding input space.

  • Since only a few integer variables are used (count, factor, higher, current, lower).

Total Space Complexity

If includes both auxiliary and total space complexity.

  • The input is a single integer n, hence input space complexity is O(1).

Total Space Complexity is O(1).

Similar questions

Now we have successfully tackled this problem, let's try these similar problems:-

1. Nth Digit

Given an integer n, return the nth digit of the infinite integer sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].

2. Count Numbers with Unique Digits

Given an integer n, return the count of all numbers with unique digits, x, where 0 <= x < 10n.