题目

The task is simple: given any positive integer $N$ , you are supposed to count the total number of 1’s in the decimal form of the integers from 1 to $N$ . For example, given $N$ being 12, there are five 1’s in 1, 10, 11, and 12.

Input Specification:

Each input file contains one test case which gives the positive $N$ ( $\le 2^{30}$ ).

Output Specification:

For each test case, print the number of 1’s in one line.

Sample Input:

1

12

Sample Output:

1

5

思路

几乎是纯数学题。求1到N所有数中1的出现次数。注意不是含1的数字出现字数，所以只要是按位计数的，就不需要考虑重复计数的事情。

总的思路就是逐位分析，假设某一位是1，统计所有小于N的数字数量，最后累加起来。

当假设是1的一位确定时，不确定的则自然是它前面（更大）和后面（更小）的位分别组成的两个数字，即我们将一个数拆成三个数字：

前缀数字 当前位 后缀数字

根据N的当前位，分类讨论当前位为不同值时，前/后缀数字可能取值范围，使得这个组成的数小于N：

  • 如果N的当前位为0：

    则只有前缀数字小于N的前缀数字，才有可能小于N（因为假设此数当前位是1，大于N的当前位了）；而后缀数字无限制，可以取0到99…9

  • 如果N的当前位为1：

    当前位与N一样，所以前缀数字如何取需要再分类讨论

    • 前缀数字等于N的前缀数字：此时前面几个数完全一样，后缀数字小于等于N的后缀数字即可
    • 前缀数字小于N的前缀数字：后缀数字无限制，可以取0到99…9

  • 如果N的当前位大于1：

    前缀数字可以取0到N的前缀数字；而后缀数字无限制，可以取0到99…9

代码

Github最新代码，欢迎交流

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

#include <stdio.h>

int main()
{
	int N, base10, lo, curr, hi, count = 0;

	scanf("%d", &N);

	/* for every digits, from lower to higher */
	for (base10 = 1; base10 <= N; base10 *= 10) {
		lo = N % base10;        /* part of the number after current digit */
		hi = N / base10 / 10;   /* part of the number before current digit */
		curr = N / base10 - hi * 10;     /* current digit */
		/* count numbers that is smaller than N and has '1' in the current digit */
		if (curr == 0)           /* count: [0~(hi-1)]1[0~9...9] */
			count += hi * base10;
		else if (curr == 1)      /* count: [0~(hi-1)]1[0~9...9] or [hi]1[0~lo] */
			count += lo + 1 + hi * base10;
		else                    /* count: [0~hi]1[0~9...9] */
			count += (hi + 1) * base10;
	}

	printf("%d\n", count);

	return 0;
}