Shulou(Shulou.com)06/01 Report--

This article introduces the relevant knowledge of "how Java calculates the number of times 1 appears in 1 to n integers". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Introduction to the topic

Find out the number of times 1 occurs in integers 1 ~ 13, and calculate the number of times 1 occurs in integers 1 ~ 1300? For this reason, he specifically counted the numbers 1, 10, 11, 12, 13 in 1-13, so they appeared six times, but there was nothing he could do about the following problems. ACMer wants you to help him and generalize the problem so that you can quickly find the number of times 1 occurs in any interval of non-negative integers (from 1 to 1 in n).

The first way to solve the problem: recursive each digital train of thought

The idea is very simple, write a for loop, from 1 to n, in the loop body to determine how many 1s this number contains

Complexity O (nlogn), the interviewer is not very happy.

Method 2: find the law.

Let N = abcde, where abcde is the number on each bit in the decimal system.

If you want to calculate the number of times one appears in the top 100, it will be affected in three ways: the number on the hundred, the number below the hundred (low), and the number of more than 100 (high).

In ①, if the number in the hundred digits is 0, the number of times a 1 may appear in the hundred digits is determined by the higher bit. For example: 12013, then we can know that the situation of 1 in 100 may be: 1100 ~ 1991100 ~ 1199pr 2100 ~ 2199jue. , 11100-11199, a total of 1200. It can be seen that it is determined by a higher digit (12) and is equal to a higher digit (12) multiplied by the current digit (100).

In ②, if the number in the hundred digits is 1, the number of times 1 in the hundred digits may be affected not only by the higher bit but also by the low bit. For example: 12113, we can know that 100 bits are affected by the high position. 11100 to 11199, a total of 1200. As in the case above, and equal to the higher digit (12) multiplied by the current digit (100). But at the same time, it is also affected by the low bit, the case of 1 in 100 is: 12100 to 12113, a total of 114, equal to the low number (113) + 1.

③ if the number on 100 is greater than 1 (2-9), then the occurrence of 1 on 100 is only determined by the higher bit, for example, 12213, then the case of 1 in 100 is 100-1991,100-11991100-2199, … , 11100 ~ 111991.12100 ~ 12199, there are 1300, and it is equal to the higher digit + 1 (12100) multiplied by the current digit (12199).

Code public int NumberOf1Between1AndN_Solution (int n) {

The number of / / 1

Int count = 0

/ / current position

Int I = 1

Int current, after, before

While ((nstroke I)! = 0) {

/ / High digit

Current = (nUnix I)

/ / current digit

Before = n / (iTun10)

/ / low digit

After = n-(nmp I) * I

/ / if 0, the number of occurrences of 1 is determined by the high bit, and the number is equal to the high digit * current digit

If (current = = 0) {

Count + = before * I

} else if (current = = 1) {

/ / if it is 1, the number of occurrences of 1 is determined by the high position and the low position, the high bit * current bit + low bit + 1

Count + = before * I + after + 1

} else {

/ / if it is greater than 1, the number of occurrences of 1 is determined by the high order, (high digit + 1) * current digit

Count + = (before + 1) * I

}

/ / move forward one bit

I = iTunes 10

}

Return count

} this is the end of the content of "how Java calculates the number of occurrences of 1 in 1 to n integers". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.