Skip to content

3490. Count Beautiful Numbers 👍

  • Time: $O(n \cdot 2^3 \cdot (n \cdot 9) \cdot (3 \cdot n \cdot 2 \cdot n \cdot 9 \cdot 9) \cdot 10) = O(n^4)$, where $n = \log r$
  • Space: $O(n \cdot 2^3 \cdot (n \cdot 9) \cdot (3 \cdot n \cdot 2 \cdot n \cdot 9 \cdot 9))$
 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
class Solution {
 public:
  int beautifulNumbers(int l, int r) {
    return count(to_string(r), 0, /*tight=*/true, /*isLeadingZero=*/true,
                 /*hasZero=*/false, /*sum=*/0, /*prod=*/1, {}) -
           count(to_string(l - 1), 0, /*tight=*/true, /*isLeadingZero=*/true,
                 /*hasZero=*/false, /*sum=*/0, /*prod=*/1, {});
  }

 private:
  int count(const string& s, int i, bool tight, bool isLeadingZero,
            bool hasZero, int sum, int prod, unordered_map<string, int>&& mem) {
    if (i == s.length()) {
      if (isLeadingZero)
        return 0;
      return (hasZero || prod % sum == 0) ? 1 : 0;
    }
    const string key = hash(i, tight, isLeadingZero, hasZero, sum, prod);
    if (!isLeadingZero && hasZero && !tight)
      return mem[key] = pow(10, s.length() - i);
    if (const auto it = mem.find(key); it != mem.end())
      return it->second;

    int res = 0;
    const int maxDigit = tight ? s[i] - '0' : 9;

    for (int d = 0; d <= maxDigit; ++d) {
      const bool nextTight = tight && (d == maxDigit);
      const bool nextIsLeadingZero = isLeadingZero && d == 0;
      const bool nextHasZero = !nextIsLeadingZero && d == 0;
      const int nextProd = nextIsLeadingZero ? 1 : prod * d;
      res += count(s, i + 1, nextTight, nextIsLeadingZero, nextHasZero, sum + d,
                   nextProd, std::move(mem));
    }

    return mem[key] = res;
  }

  string hash(int i, bool tight, bool isLeadingZero, bool hasZero, int sum,
              int prod) {
    return to_string(i) + "_" + (tight ? "1" : "0") + "_" +
           (isLeadingZero ? "1" : "0") + "_" + (hasZero ? "1" : "0") + "_" +
           to_string(sum) + "_" + to_string(prod);
  }
};

 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
class Solution {
  public int beautifulNumbers(int l, int r) {
    return count(String.valueOf(r), 0, /*tight=*/true, /*isLeadingZero=*/true,
                 /*hasZero=*/false, /*sum=*/0, /*prod=*/1, new HashMap<>()) -
        count(String.valueOf(l - 1), 0, /*tight=*/true, /*isLeadingZero=*/true,
              /*hasZero=*/false, /*sum=*/0, /*prod=*/1, new HashMap<>());
  }

  private int count(final String s, int i, boolean tight, boolean isLeadingZero, boolean hasZero,
                    int sum, int prod, Map<String, Integer> mem) {
    if (i == s.length()) {
      if (isLeadingZero)
        return 0;
      return (hasZero || prod % sum == 0) ? 1 : 0;
    }
    final String key = hash(i, tight, isLeadingZero, hasZero, sum, prod);
    if (!isLeadingZero && hasZero && !tight) {
      final int val = (int) Math.pow(10, s.length() - i);
      mem.put(key, val);
      return val;
    }
    if (mem.containsKey(key))
      return mem.get(key);

    int res = 0;
    final int maxDigit = tight ? s.charAt(i) - '0' : 9;

    for (int d = 0; d <= maxDigit; ++d) {
      final boolean nextTight = tight && (d == maxDigit);
      final boolean nextIsLeadingZero = isLeadingZero && d == 0;
      final boolean nextHasZero = !nextIsLeadingZero && d == 0;
      final int nextProd = nextIsLeadingZero ? 1 : prod * d;
      res += count(s, i + 1, nextTight, nextIsLeadingZero, nextHasZero, sum + d, nextProd, mem);
    }

    mem.put(key, res);
    return res;
  }

  private String hash(int i, boolean tight, boolean isLeadingZero, boolean hasZero, int sum,
                      int prod) {
    return i + "_" + (tight ? "1" : "0") + "_" + (isLeadingZero ? "1" : "0") + "_" +
        (hasZero ? "1" : "0") + "_" + sum + "_" + prod;
  }
}

 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:
  def beautifulNumbers(self, l: int, r: int) -> int:
    @functools.lru_cache(None)
    def dp(
        s: str,
        i: int,
        tight: bool,
        isLeadingZero: bool,
        hasZero: bool,
        sum: int,
        prod: int,
    ) -> int:
      if i == len(s):
        if isLeadingZero:
          return 0
        return 1 if hasZero or prod % sum == 0 else 0
      if not isLeadingZero and hasZero and not tight:
        return 10 ** (len(s) - i)

      res = 0
      maxDigit = int(s[i]) if tight else 9

      for d in range(maxDigit + 1):
        nextTight = tight and (d == maxDigit)
        nextIsLeadingZero = isLeadingZero and d == 0
        nextHasZero = not nextIsLeadingZero and d == 0
        nextProd = 1 if nextIsLeadingZero else prod * d
        res += dp(s, i + 1, nextTight, nextIsLeadingZero,
                  nextHasZero, sum + d, nextProd)

      return res

    return (dp(str(r), 0, tight=True, isLeadingZero=True, hasZero=False, sum=0, prod=1) -
            dp(str(l - 1), 0, tight=True, isLeadingZero=True, hasZero=False, sum=0, prod=1))