public int countDigitOne(int n) {
        if (n <= 0) return 0;

        int cnt = 0;
        int b = (int) Math.pow(10, String.valueOf(n).length() - 1);
        while (b >= 1) {
            int left = n / b, right = n % b;
            int d = left % 10;
            if (d > 1) {
                cnt += (left / 10 + 1) * b;
            } else if (d == 1) {
                cnt += left / 10 * b + right + 1;
            } else {
                cnt += left / 10 * b;
            }
            b /= 10; // divide instead of multiply to avoid overflow
        }
        return cnt;
    }