0ms c++ no-recursive solution


  • 0
    I

    The idea is same as most posts. The good thing is that we don't need to calculate log10(n) in each iteration here and it's non-recursive.

    int countDigitOne(int n) {
        if (n < 0) return 0;
        int a[10] = { 0 }, b[10] = { 1 };
        for (int i = 1; i < 10; i++) {
            b[i] = b[i - 1] * 10;
            a[i] = a[i - 1] * 10 + b[i - 1]; 
        }
        string nStr = to_string(n);
        int ans = 0;
        for (int i = 0, size = nStr.size(); i < size; i++) {
            int digit = nStr[i] - '0';
            if (digit > 1) {
                ans += a[size - i - 1] * digit + b[size - i - 1];
            } else if (digit == 1) {
                ans += a[size - i - 1] + 1;
                if (i != size - 1) ans += stoi(nStr.substr(i + 1));
            }
        }
        return ans;
    }

Log in to reply
 

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