[Algorithm] Number of Digit One

Number of Digit One

Problem Statement:

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Solution : Count by digits.

This kind of question takes more of some math rather than brutal force. It's generally a good practice to think about how can we calculate the occurrence of digit 1's at each position. To solve this let's examine some properties at each digit position.

If we are going to examine each digit of a number we need to break them into three segments: (high) curr (low), where high and low can be any arbitrary non-negative number, for example if we have number 13231 and we are looking at the 3rd bit from right to left, then high = 13, curr = 2, low = 31. We are also going to introduce base which is which is of 10's power. The base for this case is 100 which equals 10 ^ (i - 1) if we are looking at (i)th digit.

We are going to describe the three segment with high, curr, low and base for now on.

Let's first consider simple cases, let's say 200, and we are looking at 2nd digit. The possible number 1 occurring at that position is:

0     010
1     011
2     012
...
10   110
11   111
...
19   119

We could have 20 occurrences for that. And the formula for that is (high * base). This is the most basic case where the given number happen to be N * base. So how about this case, suppose we have number 1131 and we are still interested in the 2nd digit. Now the possible occurrence of 1's are:

0010
0011
...
0110
...
0119
0210
...
1110
1119

The total number of 1's equals (12 * base) which is (high + 1) * base. How about the number being 1111 will it still hold? The possible occurrences now become:

0010
0011
...
0110
...
0119
0210
...
1019
1110
1111

This occurrence of 1's equals (10 * base) + 2 which is (high * base + low + 1).  How about the number being 1101, the possible occurrences now become:

0010
0011
...
0110
...
0119
0210
...
1010
...
1019

The occurrence of 1's now becomes (10 * base) which is (high * base) and this is exactly the first simple case we discuss.

We are further prove that if we divide a number by (high) curr (low) we can calculate the possible occurrence of 1 at curr's digit postion with the following equations:

occurrence = high * base, where curr == 0
             high * base + low + 1, where curr == 1
             (high + 1) * base, where curr > 1

So we can have the following implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

class Solution { public: int countDigitOne(int n) { if (n <= 0) return 0; int base = 1; int high = n; int low = 0; long long count = 0; while (high) { int curr = high % 10; high = high / 10; printf("%d\t%d\t%d\t%d\n", high, curr, low, base); if (curr == 0) { count += high * base; } else if (curr == 1) { count += (low+1) + high * base; } else { count += (high+1) * base; } low += curr * base; base *= 10; } return count; } };