Skip to content

3348. Smallest Divisible Digit Product II

  • Time: $O(\texttt{num} + \log t)$
  • Space: $O(\texttt{num})$
  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
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
class Solution {
 public:
  string smallestNumber(string num, long long t) {
    const auto [primeCount, isDivisible] = getPrimeCount(t);
    if (!isDivisible)
      return "-1";

    const unordered_map<int, int> factorCount = getFactorCount(primeCount);
    if (sumValues(factorCount) > num.length())
      return consturct(factorCount);

    unordered_map<int, int> primeCountPrefix = getPrimeCount(num);
    int firstZeroIndex = num.find('0');
    if (firstZeroIndex == string::npos) {
      firstZeroIndex = num.length();
      if (isSubset(primeCount, primeCountPrefix))
        return num;
    }

    for (int i = num.length() - 1; i >= 0; --i) {
      const int d = num[i] - '0';
      // Remove the current digit's factors from primeCountPrefix.
      primeCountPrefix = substract(primeCountPrefix, kFactorCounts.at(d));
      const int spaceAfterThisDigit = num.length() - 1 - i;
      if (i > firstZeroIndex)
        continue;
      for (int biggerDigit = d + 1; biggerDigit < 10; ++biggerDigit) {
        // Compute the required factors after replacing with a larger digit.
        const unordered_map<int, int> factorsAfterReplacement =
            getFactorCount(substract(substract(primeCount, primeCountPrefix),
                                     kFactorCounts.at(biggerDigit)));
        // Check if the replacement is possible within the available space.
        if (sumValues(factorsAfterReplacement) <= spaceAfterThisDigit) {
          // Fill extra space with '1', if any, and construct the result.
          const int fillOnes =
              spaceAfterThisDigit - sumValues(factorsAfterReplacement);
          return num.substr(0, i) +        // Keep the prefix unchanged.
                 to_string(biggerDigit) +  // Replace the current digit.
                 string(fillOnes, '1') +   // Fill remaining space with '1'.
                 consturct(factorsAfterReplacement);
        }
      }
    }

    // No solution of the same length exists, so we need to extend the number
    // by prepending '1's and adding the required factors.
    const unordered_map<int, int> factorsAfterExtension =
        getFactorCount(primeCount);
    return string(num.length() + 1 - sumValues(factorsAfterExtension), '1') +
           consturct(factorsAfterExtension);
  }

 private:
  constexpr static unordered_map<int, unordered_map<int, int>> kFactorCounts = {
      {0, {}},       {1, {}},       {2, {{2, 1}}},         {3, {{3, 1}}},
      {4, {{2, 2}}}, {5, {{5, 1}}}, {6, {{2, 1}, {3, 1}}}, {7, {{7, 1}}},
      {8, {{2, 3}}}, {9, {{3, 2}}}};

  // Returns the prime count of t and if t is divisible by 2, 3, 5, 7.
  pair<unordered_map<int, int>, bool> getPrimeCount(long t) {
    unordered_map<int, int> count{{2, 0}, {3, 0}, {5, 0}, {7, 0}};
    for (const int prime : {2, 3, 5, 7}) {
      while (t % prime == 0) {
        t /= prime;
        ++count[prime];
      }
    }
    return {count, t == 1};
  }

  // Returns the prime count of `num`.
  unordered_map<int, int> getPrimeCount(const string& num) {
    unordered_map<int, int> count{{2, 0}, {3, 0}, {5, 0}, {7, 0}};
    for (const char d : num)
      for (const auto& [prime, freq] : kFactorCounts.at(d - '0'))
        count[prime] += freq;
    return count;
  }

  unordered_map<int, int> getFactorCount(const unordered_map<int, int>& count) {
    unordered_map<int, int> res;
    // 2^3 = 8
    const int count8 = count.at(2) / 3;
    const int remaining2 = count.at(2) % 3;
    // 3^2 = 9
    const int count9 = count.at(3) / 2;
    int count3 = count.at(3) % 2;
    // 2^2 = 4
    int count4 = remaining2 / 2;
    int count2 = remaining2 % 2;
    // Combine 2 and 3 to 6 if both are present.
    int count6 = 0;
    if (count2 == 1 && count3 == 1) {
      count2 = 0;
      count3 = 0;
      count6 = 1;
    }
    // Combine 3 and 4 to 2 and 6 if both are present.
    if (count3 == 1 && count4 == 1) {
      count2 = 1;
      count6 = 1;
      count3 = 0;
      count4 = 0;
    }
    return unordered_map<int, int>{
        {2, count2}, {3, count3},      {4, count4}, {5, count.at(5)},
        {6, count6}, {7, count.at(7)}, {8, count8}, {9, count9}};
  }

  string consturct(const unordered_map<int, int>& factors) {
    string res;
    for (int digit = 2; digit < 10; ++digit)
      res += string(factors.at(digit), '0' + digit);
    return res;
  }

  // Returns true if a is a subset of b.
  bool isSubset(const unordered_map<int, int>& a,
                const unordered_map<int, int>& b) {
    for (const auto& [key, value] : a)
      if (b.at(key) < value)
        return false;
    return true;
  }

  // Returns a - b.
  unordered_map<int, int> substract(unordered_map<int, int> a,
                                    const unordered_map<int, int>& b) {
    for (const auto& [key, value] : b)
      a[key] = max(0, a[key] - value);
    return a;
  }

  // Returns the sum of the values in `count`.
  int sumValues(const unordered_map<int, int>& count) {
    return accumulate(
        count.begin(), count.end(), 0,
        [](int acc, const pair<int, int>& p) { return acc + p.second; });
  }
};

  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
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
class Solution {
  public String smallestNumber(String num, long t) {
    Pair<Map<Integer, Integer>, Boolean> primeCountResult = getPrimeCount(t);
    Map<Integer, Integer> primeCount = primeCountResult.getKey();
    boolean isDivisible = primeCountResult.getValue();
    if (!isDivisible)
      return "-1";

    Map<Integer, Integer> factorCount = getFactorCount(primeCount);
    if (sumValues(factorCount) > num.length())
      return construct(factorCount);

    Map<Integer, Integer> primeCountPrefix = getPrimeCount(num);
    int firstZeroIndex = num.indexOf('0');
    if (firstZeroIndex == -1) {
      firstZeroIndex = num.length();
      if (isSubset(primeCount, primeCountPrefix))
        return num;
    }

    for (int i = num.length() - 1; i >= 0; --i) {
      final int d = num.charAt(i) - '0';
      // Remove the current digit's factors from primeCountPrefix.
      primeCountPrefix = subtract(primeCountPrefix, FACTOR_COUNTS.get(d));
      final int spaceAfterThisDigit = num.length() - 1 - i;
      if (i > firstZeroIndex)
        continue;
      for (int biggerDigit = d + 1; biggerDigit < 10; ++biggerDigit) {
        // Compute the required factors after replacing with a larger digit.
        Map<Integer, Integer> factorsAfterReplacement = getFactorCount(
            subtract(subtract(primeCount, primeCountPrefix), FACTOR_COUNTS.get(biggerDigit)));
        // Check if the replacement is possible within the available space.
        if (sumValues(factorsAfterReplacement) <= spaceAfterThisDigit) {
          // Fill extra space with '1', if any, and construct the result.
          final int fillOnes = spaceAfterThisDigit - sumValues(factorsAfterReplacement);
          return num.substring(0, i) + // Keep the prefix unchanged.
              biggerDigit +            // Replace the current digit.
              "1".repeat(fillOnes) + // Fill remaining space with '1'.
              construct(factorsAfterReplacement);
        }
      }
    }

    // No solution of the same length exists, so we need to extend the number
    // by prepending '1's and adding the required factors.
    Map<Integer, Integer> factorsAfterExtension = getFactorCount(primeCount);
    return "1".repeat(num.length() + 1 - sumValues(factorsAfterExtension)) +
        construct(factorsAfterExtension);
  }

  private static final Map<Integer, Map<Integer, Integer>> FACTOR_COUNTS = Map.of(
      0, Map.of(), 1, Map.of(), 2, Map.of(2, 1), 3, Map.of(3, 1), 4, Map.of(2, 2), 5, Map.of(5, 1),
      6, Map.of(2, 1, 3, 1), 7, Map.of(7, 1), 8, Map.of(2, 3), 9, Map.of(3, 2));

  // Returns the prime count of t and if t is divisible by 2, 3, 5, 7.
  private Pair<Map<Integer, Integer>, Boolean> getPrimeCount(long t) {
    Map<Integer, Integer> count = new HashMap<>(Map.of(2, 0, 3, 0, 5, 0, 7, 0));
    for (int prime : new int[] {2, 3, 5, 7}) {
      while (t % prime == 0) {
        t /= prime;
        count.put(prime, count.get(prime) + 1);
      }
    }
    return new Pair<>(count, t == 1);
  }

  // Returns the prime count of `num`.
  private Map<Integer, Integer> getPrimeCount(String num) {
    Map<Integer, Integer> count = new HashMap<>(Map.of(2, 0, 3, 0, 5, 0, 7, 0));
    for (final char c : num.toCharArray()) {
      Map<Integer, Integer> digitFactors = FACTOR_COUNTS.get(c - '0');
      for (Map.Entry<Integer, Integer> entry : digitFactors.entrySet()) {
        final int prime = entry.getKey();
        final int freq = entry.getValue();
        count.merge(prime, freq, Integer::sum);
      }
    }
    return count;
  }

  private Map<Integer, Integer> getFactorCount(Map<Integer, Integer> count) {
    // 2^3 = 8
    final int count8 = count.get(2) / 3;
    final int remaining2 = count.get(2) % 3;
    // 3^2 = 9
    final int count9 = count.get(3) / 2;
    int count3 = count.get(3) % 2;
    // 2^2 = 4
    int count4 = remaining2 / 2;
    int count2 = remaining2 % 2;
    // Combine 2 and 3 to 6 if both are present
    int count6 = 0;
    if (count2 == 1 && count3 == 1) {
      count2 = 0;
      count3 = 0;
      count6 = 1;
    }
    // Combine 3 and 4 to 2 and 6 if both are present
    if (count3 == 1 && count4 == 1) {
      count2 = 1;
      count6 = 1;
      count3 = 0;
      count4 = 0;
    }
    return Map.of(2, count2, 3, count3, 4, count4, 5, count.get(5), 6, count6, 7, count.get(7), 8,
                  count8, 9, count9);
  }

  private String construct(Map<Integer, Integer> factors) {
    StringBuilder sb = new StringBuilder();
    for (int digit = 2; digit < 10; ++digit)
      sb.append(String.valueOf(digit).repeat(factors.get(digit)));
    return sb.toString();
  }

  // Returns true if a is a subset of b.
  private boolean isSubset(Map<Integer, Integer> a, Map<Integer, Integer> b) {
    for (Map.Entry<Integer, Integer> entry : a.entrySet())
      if (b.get(entry.getKey()) < entry.getValue())
        return false;
    return true;
  }

  // Returns a - b.
  private Map<Integer, Integer> subtract(Map<Integer, Integer> a, Map<Integer, Integer> b) {
    Map<Integer, Integer> res = new HashMap<>(a);
    for (Map.Entry<Integer, Integer> entry : b.entrySet()) {
      final int key = entry.getKey();
      final int value = entry.getValue();
      res.put(key, Math.max(0, res.get(key) - value));
    }
    return res;
  }

  // Returns the sum of the values in `count`.
  private int sumValues(Map<Integer, Integer> count) {
    return count.values().stream().mapToInt(Integer::intValue).sum();
  }
}

 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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
FACTOR_COUNTS = {
    0: collections.Counter(),
    1: collections.Counter(),
    2: collections.Counter([2]),
    3: collections.Counter([3]),
    4: collections.Counter([2, 2]),
    5: collections.Counter([5]),
    6: collections.Counter([2, 3]),
    7: collections.Counter([7]),
    8: collections.Counter([2, 2, 2]),
    9: collections.Counter([3, 3]),
}


class Solution:
  def smallestNumber(self, num: str, t: int) -> str:
    primeCount, isDivisible = self._getPrimeCount(t)
    if not isDivisible:
      return '-1'

    factorCount = self._getFactorCount(primeCount)
    if sum(factorCount.values()) > len(num):
      return ''.join(factor * freq for factor, freq in factorCount.items())

    primeCountPrefix = sum((FACTOR_COUNTS[int(c)]
                            for c in num), start=collections.Counter())
    firstZeroIndex = next((i for i, d in enumerate(num) if d == '0'), len(num))
    if firstZeroIndex == len(num) and primeCount <= primeCountPrefix:
      return num

    for i, c in reversed(list(enumerate(num))):
      d = int(c)
      # Remove the current digit's factors from primeCountPrefix.
      primeCountPrefix -= FACTOR_COUNTS[d]
      spaceAfterThisDigit = len(num) - 1 - i
      if i <= firstZeroIndex:
        for biggerDigit in range(d + 1, 10):
          # Compute the required factors after replacing with a larger digit.
          factorsAfterReplacement = self._getFactorCount(
              primeCount - primeCountPrefix - FACTOR_COUNTS[biggerDigit]
          )
          # Check if the replacement is possible within the available space.
          if sum(factorsAfterReplacement.values()) <= spaceAfterThisDigit:
            # Fill extra space with '1', if any, and construct the result.
            fillOnes = spaceAfterThisDigit - sum(
                factorsAfterReplacement.values())
            return (
                num[:i]  # Keep the prefix unchanged.
                + str(biggerDigit)  # Replace the current digit.
                + '1' * fillOnes  # Fill remaining space with '1'.
                + ''.join(factor * freq for factor,
                          freq in factorsAfterReplacement.items())
            )

    # No solution of the same length exists, so we need to extend the number
    # by prepending '1's and adding the required factors.
    factorCount = self._getFactorCount(primeCount)
    return (
        '1' * (len(num) + 1 - sum(factorCount.values()))
        + ''.join(factor * freq for factor, freq in factorCount.items())
    )

  def _getPrimeCount(self, t: int) -> tuple[dict[int, int], bool]:
    """
    Returns the count of prime factors of t and if t is divisible by 2, 3, 5, 7.
    """
    count = collections.Counter()
    for prime in [2, 3, 5, 7]:
      while t % prime == 0:
        t //= prime
        count[prime] += 1
    return count, t == 1

  def _getFactorCount(self, count: dict[int, int]) -> dict[str, int]:
    """Returns the required factors to form the smallest number."""
    count8, remaining2 = divmod(count[2], 3)  # 2^3 = 8
    count9, count3 = divmod(count[3], 2)  # 3^2 = 9
    count4, count2 = divmod(remaining2, 2)  # 2^2 = 4
    # Combine 2 and 3 to 6 if both are present.
    count2, count3, count6 = ((0, 0, 1) if count2 == 1 and count3 == 1
                              else (count2, count3, 0))
    # Combine 3 and 4 to 2 and 6 if both are present.
    count2, count6, count3, count4 = ((1, 1, 0, 0)
                                      if count3 == 1 and count4 == 1
                                      else (count2, count6, count3, count4))
    return {'2': count2, '3': count3, '4': count4, '5': count[5],
            '6': count6, '7': count[7], '8': count8, '9': count9}