Share my solution: c++, 0ms


  • 0
    Z

    Take the number 987654321 as input.

    for [0,10^8) there are 810^8/10 ones ,because there 810^8 digits and each number (0,1,2,3,4,5,6,7,8,9) has the same probability to appear so the number of ones is 8*10^8/10;

    [210^8,310^8), [310^8,410^8), ... , [810^8,910^8) all have 8*10^8/10 ones;

    [10^8,210^8) has 810^8/10 + 10^8 ones (easy to understand)

    so just remain [9*10^8,987654321], which equals to [0,87654321], recursion.

    Just be aware that the variable num in Solution() should be long long. ^-^

    class Solution {
    public:
    	int countDigitOne(int n) {
    		if (n <= 0) return 0;
    		int len = 0;
    		int num = n;
    		while (num) {
    			len++;
    			num /= 10;
    		}
    		int base = 1;
    		for (int i = 0; i<len - 1; i++) base *= 10;
    		int firstdigit = n / base;
    		int ret = countDigitOne(n%base);
    		if (firstdigit == 1) return a[len - 1] + n%base + 1 + ret;
    		else return firstdigit*a[len - 1] + base + ret;
    	}
    	Solution() {
    		for (int i = 0; i<10; i++) {
    			long long num = 1;
    			for (int j = 0; j<i; j++) num *= 10;
    			a.push_back(i*num / 10);
    		}
    	}
    private:
    	vector<int> a;
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.