43. Number of occurrences of 1 in 1 ~ n integers

The finger of the sword Offer 43. 1～n In integers 1 Number of occurrences

Ideas ： mathematics

Set the number n It's a x digit , remember n Of the i Position as $n_i$, Then you can put n Written as $n_x{n}_{x-1}\cdots n_2{n}_1$;

• remember $n_i$ Is the current bit , Write it down as cur
• remember $n_{i-1}{n}_{i-2}\cdots n_2{n}_1$ by low
• remember $n_x{n}_{x-1}\cdots n_{i+2}{n}_{i+1}$ by high
• remember $10^i$ It's a factor , Write it down as digit

According to the current bit cur Different , There are three situations ：

1.cur=0 when ：cur appear 1 The number of high decision , The formula is ：

$high\times digit$​

2.cur=1 when ：cur appear 1 The number of times is determined by high and low decision , The formula is ：

$high\times digit+low+1$

3.cur=2,3,…9 when ：cur appear 1 The number of high decision , The formula is ：

$(high+1)\times digit$

class Solution {
public:
    int countDigitOne(int n) {
        int high=n/10,cur=n%10,low=0,res=0;
        long digit=1;
        while(high||cur){
            if(cur==0) res+=high*digit;
            else if(cur==1) res+=high*digit+low+1;
            else res+=(high+1)*digit;

            low+=digit*cur,cur=high%10,high/=10,digit*=10;
        }
        return res;
    }
};

Time complexity O(logn)

Spatial complexity O(1)