Make writing a habit together! This is the 7th day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

I. Problem description

Given an integer n, count the number of occurrences of the number 1 in all non-negative integers less than or equal to n.

The number of 1’s

Two, the title requirements

Sample 1

Input: n = 13 Output: 6Copy the code

The sample 2

Input: n = 0 Output: 0Copy the code

inspection

1. Mathematical ideas and timeout optimization 2. It is recommended to use 15~35minCopy the code

Third, problem analysis

As soon as I got hold of this question, I felt something was wrong. It was obviously a very simple question, but it only needed circular statistics, but Likou actually labeled it as difficult.

class Solution {
public:
    int countDigitOne(int n) {
        int i,k,ans=0;// Initialize the data
        for(i=1; i<=n; i++)/ / loop 1 ~ n
        {
            k=i;
            while(k)// Whether the digit contains 1
            {
                if(k%10= =1)
                    ans++;/ / count
                k=k/10; }}return ans;// Output the result}};Copy the code

So, my code will definitely time out.

It is found that this is a regular problem:

The rules are as follows, drawing on the ideas of big men:

/** Count the number of 1s in the first digit: 1+(n-1)/10 The number of 1s in the second digit: (1+(n/10-1)/10)*10 The number of 1s in the third digit: (1+(n/100-1)/10)*100...... (1+(n/(10^k)-1)/10)*(10^k) (1+(n/(10^k)-1)/10)*(10^k) (1+(n/(10^k)-1)/10)*(10^k) (1+(n/(10^k)-1)/10)*(10^k) (1+(n/(10^k)-1) *(10^kCopy the code

Four, coding implementation

class Solution {
public:
    int countDigitOne(int n) {
        long long k = 1,ans = 0;// Initialize the data
        while (n >= k){
            ans += (1+(n/k- 1) /10)*k;/ / count
            if (n/k%10= =1) ans = ans-k+1+n%k;// The current bit is 1, minus the data
            k *= 10;
        }
        return ans;// Output the result}};Copy the code

V. Test results