3747. Count Distinct Integers After Removing Zeros

You are given a positive integer n.

For every integer x from 1 to n, we write down the integer obtained by removing all zeros from the decimal representation of x.

Return an integer denoting the number of distinct integers written down.

public long countDistinct(long n) {
    char[] s = Long.toString(n).toCharArray();
    int m = s.length;

    // 计算长度小于 m 的不含 0 的整数个数
    // 9^1 + 9^2 + ... + 9^(m-1) = (9^m - 9) / 8
    long pow9 = (long) Math.pow(9, m);
    long ans = (pow9 - 9) / 8;

    // 计算长度恰好等于 m 的不含 0 的整数个数
    for (int i = 0; i < m; i++) {
        char d = s[i];
        if (d == '0') { // 只能填 0，不合法，跳出循环
            break;
        }
        // 这一位填 1 到 d-1，后面的数位可以随便填 1 到 9
        int v = d - '0';
        if (i != m - 1) {
            v--; // 非最低位不能等于 d
        }
        pow9 /= 9;
        ans += v * pow9;
        // 然后，这一位填 d，继续遍历
    }

    return ans;
}