Number of Digit One

Updated on 03 July, 2025
Number of Digit One header image

Problem Statement

The task involves determining the frequency of the digit '1' in the decimal representation of every integer from 0 up to and including a given integer 'n'. This requires scanning each integer within this range and counting how many times the digit '1' appears. For instance, if the supplied integer 'n' is 13, we consider each number from 0 to 13 and count each occurrence of '1'. The challenge demands efficiency in calculating this count, given constraints on the values of 'n'.

Examples

Example 1

Input:

n = 13

Output:

6

Example 2

Input:

n = 0

Output:

0

Constraints

  • 0 <= n <= 109

Approach and Intuition

The solution to the problem can be approached by understanding the frequency of a specific digit in each decimal place across the range of numbers we are interested in. Below is an intuition on how to approach the counting of digit '1' in all numbers from 0 to 'n'.

  1. Direct count through iteration:
    • A naive approach would be to iterate through all numbers from 0 to 'n', convert them to strings, and count the occurrences of the character '1'. This is straightforward but may not perform well with the upper constraint limits.

Example walk-through from the given examples:

  • For n = 13, we analyse:
    • 0 to 13: 1, 10, 11 (contains two '1's), 12, 13, making for a total of 6 occurrences of '1'.
  • For n = 0, there are zero occurrences of '1'.

This naive method involves quite a bit of repeated work and might run slowly for very large numbers due to the magnitude of operations.

  1. Efficient mathematical approach:
    • This method involves a more mathematical approach where each digit's place (units, tens, hundreds, etc.) is systematically analysed across all numbers from 0 to 'n'. We consider:
      • The current value of the digit,
      • The value of all digits to the right,
      • The value of all digits to the left.
    • Count the '1's contributed by each digit position by considering combinations of lower, current, and higher digits for every position from the least significant to the most significant.

Approaching this problem by breaking down each digit's contribution across the entire range requires understanding the structure of numbers but significantly cuts down on the brute force checking of every number's content, making use of patterns in how often each digit position contributes a '1'. This is most suitable given the constraint limits where 'n' can be as large as 1,000,000,000.

Solutions

  • C++
cpp
int numberOfOnes(int num) {
    int totalOnes = 0;
    for (long long base = 1; base <= num; base *= 10) {
        long long factor = base * 10;
        totalOnes += (num / factor) * base + min(max(num % factor - base + 1, 0LL), base);
    }
    return totalOnes;
}

The provided solution in C++ aims to solve the problem of counting the number of digit ones in all numbers from 1 to a given number num. The function defined, numberOfOnes, calculates the total occurrences of the digit one using an efficient mathematical computation without the need to iterate through each and every number manually.

  • Initialize the totalOnes variable to store the count of digit ones.
  • Use a for loop where base represents each positional place (units, tens, hundreds, etc.) in base-10 numeral system. This loop continues as long as base is less than or equal to num.
  • For each position represented by base, calculate the total sets of numbers each base can cover using the formula (num / factor) * base where factor is ten times the current base.
  • Adjust for the extra ones that appear because of the remainder terms using the condition min(max(num % factor - base + 1, 0LL), base).
  • Sum these values to get totalOnes.

This method efficiently calculates the count using properties of numbers in decimal representation and mathematical division, avoiding brute-force counting which would considerably increase the computational cost.

Comments

No comments yet.