PAT Class A: 1049 Counting Ones

Title description:

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:

12

Sample Output:

5

Code length limit

16 KB

Time limit

400 ms

Memory Limit

64MB

Subject to the effect:

Given an n, find how many 1s appear from 0 to n

Things to solve the problem:

This question is still a bit complicated. I looked at other people's code. The basic idea is to consider each bit, that is, to calculate how many numbers this bit is 1, and use now to represent the value of the current bit, and left isThe number on the left, right is the number on the right, and a is the number of digits in the current digit, taking 3105 as an example:

• When now>=2, for example, it is divided into 310 5 0. At this time, now=5 means that (0~310)1 can be taken. The current bit of these numbers is 1, res+=(left+1)*a
• When now==1, such as 3 1 05, the number after 1 cannot be taken to a, but only to the right, so res+=left*a+right+1
• When now==0, such as 31 0 5, the current bit can only take 1 when (0~30), so res+=left*a

Python3 code:

n = int(input())left,right,now,a = 0,0,0,1res = 0while n // a :left = n // (a*10)right = n % anow = n // a % 10if now == 0 : res += left * aelif now == 1 : res += left * a + 1 + rightelse : res += (left+1) * aa *= 10print(res)