My C++ solution (just scan each digit from right to left)


  • -1
    D

    It is simple, just scan each digit from right to left, In the following code, curDigit is the digit to be checked, curLevel is the weight of that digit (e.g. 1, 10, 100, 1000, ...), residual is n%curLevel + 1, numLeft = n/(curLevel * 10). The only trick is when curDigit == 0, the '1' on that digit is curLevel * numLeft, if curDigit ==1, the '1' on that digit is curLevel * numLeft + residual, otherwise curLevel * (numLeft+1)

    It can be easily extended to "count K" problem (k =0, 1, 2, ...9), just change K value

       class Solution {
        public:
            int countDigitOne(int n) {
                int numLeft = n, curDigit, curLevel = 1, residual, res = 0, K = 1;
                while(numLeft>0)
                {
                    residual = (n % curLevel) + 1;
                    curDigit = numLeft % 10;
                    numLeft /= 10; 
                    if(curDigit>=K) res += curDigit>K?curLevel:residual;
                    res += curLevel* numLeft;
                    curLevel *=10;
                }
                return res;
            }
        };

Log in to reply
 

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