# The number of occurrences of 1 in an integer interval ### Train of thought 1

The simplest method is to find the number of 1 in each number from 1 to n respectively. Since the number of digits of the integer n is O(logn), we need to judge how many ones there are in a number, and we need to judge whether each bit is 1, so a number needs to judge O(logn) times, and there are n numbers in total, so the time complexity of this method is O(nlogn).

```/*
*      Accumulates the number of occurrences of each integer 1 in 1 to n.
*      Each time, judge whether the current bit is 1 by finding the remainder of 10
*/
public int countNum(int n){
int number = 0;
for(int i = 1;i<= n;i++){
number+=numberOf1(i);
}
return number;
}
//Directly returns the 1 contained in the current number
public int numberOf1(int n){
int number =0;
while(n!=0){
if(n %10 == 1)
number++;
n = n/10;
}
return number;
}
```

### Train of thought 2

Consider everyone,

1) This bit is greater than 1, and the number of 1 in this bit is ([n/10^(b+1]+1)*10^b
2) This bit is equal to 0, which is ([n/10^(b+1)])*10^b
3) This bit is equal to 1, plus n mod 10^b + 1 on the basis of 0

For example: 30143
Since 3 > 1, the number of times that 1 appears on a bit is (3014 + 1) * 1
Since 4 > 1, the number of occurrences of 1 on the tens is (301 + 1) × 10
Since 1 = 1, the number of occurrences of 1 in the hundreds is (30 + 0) × 100 + (43 + 1)
Since 0 < 1, the number of times of occurrence of 1 on the 1000 bit is (3 + 0) × 1000

Note: for example, the occurrence of one hundred is 100-199, and the meaning of * 100 is 100-199100 times in a single step, * 30 is due to the occurrence of 30 times of 100-199, + (43 + 1) is due to the incompleteness of the last 301 * *.

The schematic diagram of the whole process is as follows: It should be noted that since the maximum input data required by the test system is 1000000000, int will overflow and long long will be used. In addition, a may be larger than b, but there is no explanation. It's a bit of a pit.

```    /*
*      According to the law of numbers, count the number of 1 from 1 to the two ends of the interval, and then subtract
*      For example, count(a,b)=count(0,b)-count(0,a-1)
*/
public long countNum1(long num) {
if(num<=0) return 0;
long count  = 0;//Count the total number of occurrences of 1
long current;//Value of current bit
long base = 10;//Base of current bit
long remain = 0;//When the current bit is 1, the number remaining after the current bit, for example, 132, then remain=32

while(num>0) {
//Current bit
current = num%10;
//Count the possible values of all bits on the left of the current bit, such as 3012. If the current bit is 2, num=302
num = num/10;
//Determine the number of times the current bit may appear 1 according to the value of the current bit
if(current > 1) {
count += (num+1)*base;
}else if(current==1) {
count += (num*base + remain + 1);
}else {
count += num*base;
}

//Incomplete partial values may be needed to solve the next bit
remain += current*base;
base *= 10;
}
return count;
}

//Find the number of occurrences of 1 in the specified interval
public long count(long a,long b) {
long result;
if(a>b) {
result = countNum1(a) - countNum1(b-1);
}else {
result = countNum1(b) - countNum1(a-1);
}
return result;
}```

Added by christophe on Fri, 03 Jan 2020 03:34:53 +0200