3348. Smallest Divisible Digit Product II LeetCode Solution
In this guide, you will get 3348. Smallest Divisible Digit Product II LeetCode Solution with the best time and space complexity. The solution to Smallest Divisible Digit Product II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Smallest Divisible Digit Product II
You are given a string num which represents a positive integer, and an integer t.
A number is called zero-free if none of its digits are 0.
Return a string representing the smallest zero-free number greater than or equal to num such that the product of its digits is divisible by t. If no such number exists, return “-1”.
Example 1:
Input: num = “1234”, t = 256
Output: “1488”
Explanation:
The smallest zero-free number that is greater than 1234 and has the product of its digits divisible by 256 is 1488, with the product of its digits equal to 256.
Example 2:
Input: num = “12355”, t = 50
Output: “12355”
Explanation:
12355 is already zero-free and has the product of its digits divisible by 50, with the product of its digits equal to 150.
Example 3:
Input: num = “11111”, t = 26
Output: “-1”
Explanation:
No number greater than 11111 has the product of its digits divisible by 26.
Constraints:
2 <= num.length <= 2 * 105
num consists only of digits in the range ['0', '9'].
num does not contain leading zeros.
1 <= t <= 1014
Complexity Analysis
Time Complexity: O(\texttt{num} + \log t)
Space Complexity: O(\texttt{num})
3348. Smallest Divisible Digit Product II LeetCode Solution in C++
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 subtotal, const pair<int, int>& p) {
return subtotal + p.second;
});
}
}; /* code provided by PROGIEZ */
3348. Smallest Divisible Digit Product II LeetCode Solution in Java
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, kFactorCounts.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), kFactorCounts.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>> kFactorCounts = Map.of(
, 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),
, 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 = kFactorCounts.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();
}
} // code provided by PROGIEZ
3348. Smallest Divisible Digit Product II LeetCode Solution in Python
kFactorCounts = {
: collections.Counter(),
: collections.Counter(),
: collections.Counter([2]),
: collections.Counter([3]),
: collections.Counter([2, 2]),
: collections.Counter([5]),
: collections.Counter([2, 3]),
: collections.Counter([7]),
: collections.Counter([2, 2, 2]),
: 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((kFactorCounts[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 -= kFactorCounts[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 - kFactorCounts[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} # code by PROGIEZ
