Skip to content

3747. Count Distinct Integers After Removing Zeros

Description

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.

 

Example 1:

Input: n = 10

Output: 9

Explanation:

The integers we wrote down are 1, 2, 3, 4, 5, 6, 7, 8, 9, 1. There are 9 distinct integers (1, 2, 3, 4, 5, 6, 7, 8, 9).

Example 2:

Input: n = 3

Output: 3

Explanation:

The integers we wrote down are 1, 2, 3. There are 3 distinct integers (1, 2, 3).

 

Constraints:

  • 1 <= n <= 1015

Solutions

Solution 1: Digit DP

The problem essentially asks us to count the number of integers in the range \([1, n]\) that do not contain the digit 0. We can solve this problem using digit DP.

We design a function \(\text{dfs}(i, \text{zero}, \text{lead}, \text{limit})\), which represents the number of valid solutions when we are currently processing the \(i\)-th digit of the number. We use \(\text{zero}\) to indicate whether a non-zero digit has appeared in the current number, \(\text{lead}\) to indicate whether we are still processing leading zeros, and \(\text{limit}\) to indicate whether the current number is constrained by the upper bound. The answer is \(\text{dfs}(0, 0, 1, 1)\).

In the function \(\text{dfs}(i, \text{zero}, \text{lead}, \text{limit})\), if \(i\) is greater than or equal to the length of the number, we can check \(\text{zero}\) and \(\text{lead}\). If \(\text{zero}\) is false and \(\text{lead}\) is false, it means the current number does not contain 0, so we return \(1\); otherwise, we return \(0\).

For \(\text{dfs}(i, \text{zero}, \text{lead}, \text{limit})\), we can enumerate the value of the current digit \(d\), then recursively calculate \(\text{dfs}(i+1, \text{nxt\_zero}, \text{nxt\_lead}, \text{nxt\_limit})\), where \(\text{nxt\_zero}\) indicates whether a non-zero digit has appeared in the current number, \(\text{nxt\_lead}\) indicates whether we are still processing leading zeros, and \(\text{nxt\_limit}\) indicates whether the current number is constrained by the upper bound. If \(\text{limit}\) is true, then \(up\) is the upper bound of the current digit; otherwise, \(up\) is \(9\).

The time complexity is \(O(\log_{10} n \times D)\) and the space complexity is \(O(\log_{10} n)\), where \(D\) represents the count of digits from 0 to 9.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def countDistinct(self, n: int) -> int:
        @cache
        def dfs(i: int, zero: bool, lead: bool, lim: bool) -> int:
            if i >= len(s):
                return 1 if (not zero and not lead) else 0
            up = int(s[i]) if lim else 9
            ans = 0
            for j in range(up + 1):
                nxt_zero = zero or (j == 0 and not lead)
                nxt_lead = lead and j == 0
                nxt_lim = lim and j == up
                ans += dfs(i + 1, nxt_zero, nxt_lead, nxt_lim)
            return ans

        s = str(n)
        return dfs(0, False, True, True)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    private char[] s;
    private Long[][][][] f;

    public long countDistinct(long n) {
        s = String.valueOf(n).toCharArray();
        f = new Long[s.length][2][2][2];
        return dfs(0, 0, 1, 1);
    }

    private long dfs(int i, int zero, int lead, int limit) {
        if (i == s.length) {
            return (zero == 0 && lead == 0) ? 1 : 0;
        }

        if (limit == 0 && f[i][zero][lead][limit] != null) {
            return f[i][zero][lead][limit];
        }

        int up = limit == 1 ? s[i] - '0' : 9;
        long ans = 0;
        for (int d = 0; d <= up; d++) {
            int nxtZero = zero == 1 || (d == 0 && lead == 0) ? 1 : 0;
            int nxtLead = (lead == 1 && d == 0) ? 1 : 0;
            int nxtLimit = (limit == 1 && d == up) ? 1 : 0;
            ans += dfs(i + 1, nxtZero, nxtLead, nxtLimit);
        }

        if (limit == 0) {
            f[i][zero][lead][limit] = ans;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    long long countDistinct(long long n) {
        string s = to_string(n);
        int m = s.size();
        static long long f[20][2][2][2];
        memset(f, -1, sizeof(f));

        auto dfs = [&](this auto&& dfs, int i, int zero, int lead, int limit) -> long long {
            if (i == m) {
                return (zero == 0 && lead == 0) ? 1 : 0;
            }
            if (!limit && f[i][zero][lead][limit] != -1) {
                return f[i][zero][lead][limit];
            }

            int up = limit ? (s[i] - '0') : 9;
            long long ans = 0;
            for (int d = 0; d <= up; d++) {
                int nxtZero = zero || (d == 0 && !lead);
                int nxtLead = lead && d == 0;
                int nxtLimit = limit && d == up;
                ans += dfs(i + 1, nxtZero, nxtLead, nxtLimit);
            }

            if (!limit) f[i][zero][lead][limit] = ans;
            return ans;
        };

        return dfs(0, 0, 1, 1);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
func countDistinct(n int64) int64 {
    s := []byte(fmt.Sprint(n))
    m := len(s)
    var f [20][2][2][2]int64
    for i := range f {
        for j := range f[i] {
            for k := range f[i][j] {
                for t := range f[i][j][k] {
                    f[i][j][k][t] = -1
                }
            }
        }
    }

    var dfs func(i, zero, lead, limit int) int64
    dfs = func(i, zero, lead, limit int) int64 {
        if i == m {
            if zero == 0 && lead == 0 {
                return 1
            }
            return 0
        }

        if limit == 0 && f[i][zero][lead][limit] != -1 {
            return f[i][zero][lead][limit]
        }

        up := 9
        if limit == 1 {
            up = int(s[i] - '0')
        }

        var ans int64 = 0
        for d := 0; d <= up; d++ {
            nxtZero := zero
            if d == 0 && lead == 0 {
                nxtZero = 1
            }
            nxtLead := 0
            if lead == 1 && d == 0 {
                nxtLead = 1
            }
            nxtLimit := 0
            if limit == 1 && d == up {
                nxtLimit = 1
            }
            ans += dfs(i+1, nxtZero, nxtLead, nxtLimit)
        }

        if limit == 0 {
            f[i][zero][lead][limit] = ans
        }
        return ans
    }

    return dfs(0, 0, 1, 1)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function countDistinct(n: number): number {
    const s = n.toString();
    const m = s.length;

    const f: number[][][][] = Array.from({ length: m }, () =>
        Array.from({ length: 2 }, () => Array.from({ length: 2 }, () => Array(2).fill(-1))),
    );

    const dfs = (i: number, zero: number, lead: number, limit: number): number => {
        if (i === m) {
            return zero === 0 && lead === 0 ? 1 : 0;
        }

        if (limit === 0 && f[i][zero][lead][limit] !== -1) {
            return f[i][zero][lead][limit];
        }

        const up = limit === 1 ? parseInt(s[i]) : 9;
        let ans = 0;
        for (let d = 0; d <= up; d++) {
            const nxtZero = zero === 1 || (d === 0 && lead === 0) ? 1 : 0;
            const nxtLead = lead === 1 && d === 0 ? 1 : 0;
            const nxtLimit = limit === 1 && d === up ? 1 : 0;
            ans += dfs(i + 1, nxtZero, nxtLead, nxtLimit);
        }

        if (limit === 0) {
            f[i][zero][lead][limit] = ans;
        }
        return ans;
    };

    return dfs(0, 0, 1, 1);
}

Comments