Number of Digit One

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.

2. 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

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;
}