PAT-Advanced-1049. Counting Ones

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 (<=230).

Output Specification:

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

Sample Input:

Sample Output:

The task is not simple. 试了几次才将遗漏的部分补上……

对某个数 Counting Ones 的话,可以针对每一位依次进行,计算该位为一时共有多少个数。

以 XXXXXYZZ 为例,现关注第 2 位。

  • Y>1 时,有 ( XXXXX + 1 ) * 10^( ZZ的位数 ) 个第 2 位为 1 的数字;
  • Y==1 时,则有 ZZ + ( XXXXX ) * 10^( ZZ的位数 ) 个第 2 位为 1 的数字;
  • Y==0 时,则有  ( XXXXX ) * 10^( ZZ的位数 ) 个第 2 位为 1 的数字。

代码如下:

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注