[mark] A general case C++ Template for the k is any one of range [0-9]


  • 1

    Just like others' post, we just check all the possible position one by one, for each position, we need to check the left part and the right part seperately.

    Here is the AC implementation .....

    class Solution {
    public:
        int countDigitOne(int n) {
            long long result = 0;
            int left = n, right = 1, remain = 0;
            while(left > 0) {
                int digit = left % 10;
                left = left / 10;
                if(digit == 1) {
                    /** [0,left) **/
                    result += left * right;
                    /** left **/
                    result += remain + 1;
                } else if(digit == 0) {
                    result += left * right;
                } else {
                    result += (left + 1) * right;
                }
                remain += digit * right;
                right *= 10;
            }
            return result;
        }
    };
    

    Here is a general version C++ implementation, we can count the occurence of any number k ( 0 - 9) in the range from 0 to n.

    The corner case is that when k == 0, if the position is from the 100, then the number start with "0" is invalid .

    So we need to add this line to avoid the special case :

                if(k == 0 && multiplier > 1) {
                      cnt -= multiplier;
                }
    

    Here is the C++ implementation

    class Solution {
    public:
        /*
         * param k : As description.
         * param n : As description.
         * return: How many k's between 0 and n.
         */
        int digitCounts(int k, int n) {
            int cnt = 0;
            int multiplier = 1, left_part = n, right_part = 0;
            if(n == 0) {
                return k < 1;
            }
    
            while (left_part > 0) {
                int digit = left_part % 10;
                left_part /= 10;
    
                if(digit == k) {
                    cnt += left_part * multiplier;
                    cnt += right_part + 1;
                } else if (digit < k) {
                    cnt += left_part * multiplier;
                } else {
                    cnt += (left_part + 1) * multiplier;
                }
                /** this part is really tricky **/
                if(k == 0 && multiplier > 1) {
                    cnt -= multiplier;
                }
                right_part += digit * multiplier;
                multiplier *= 10;
            }
            return cnt;
        }
    };

Log in to reply
 

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