面试题 17.06

Write a method to count the number of 2s that appear in all the numbers between 0 and n (inclusive).

Example:

Input: 25 Output: 9 Explanation: (2, 12, 20, 21, 22, 23, 24, 25)(Note that 22 counts for two 2s.) Note:

n <= 10^9

Solutions

• The same as problem 233, 1067

• math

class Solution {
public:
    int numd(int n, int d) {
        int res = 0;
        for (long base = 10; base / 10 <= n; base *= 10) {
            long cnt = base / 10;
            res += (n / base) * cnt + min(max(n % base - d * cnt + 1, 0l), cnt);
            if (d == 0)
                res -= base;
        }
        return res;
    }
    int numberOf2sInRange(int n) {
        return numd(n, 2);
    }
};