3348. Smallest Divisible Digit Product II
Description
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 * 105numconsists only of digits in the range['0', '9'].numdoes not contain leading zeros.1 <= t <= 1014
Solutions
Solution 1
Python3
Java
C++
Go
func smallestNumber(num string, t int64) string {
primeCount, isDivisible := getPrimeCount(t)
if !isDivisible {
return "-1"
}
factorCount := getFactorCount(primeCount)
if sumValues(factorCount) > len(num) {
return construct(factorCount)
}
primeCountPrefix := getPrimeCountFromString(num)
firstZeroIndex := strings.Index(num, "0")
if firstZeroIndex == -1 {
firstZeroIndex = len(num)
if isSubset(primeCount, primeCountPrefix) {
return num
}
}
for i := len(num) - 1; i >= 0; i-- {
d := int(num[i] - '0')
primeCountPrefix = subtract(primeCountPrefix, kFactorCounts[d])
spaceAfterThisDigit := len(num) - 1 - i
if i > firstZeroIndex {
continue
}
for biggerDigit := d + 1; biggerDigit < 10; biggerDigit++ {
factorsAfterReplacement := getFactorCount(
subtract(subtract(primeCount, primeCountPrefix), kFactorCounts[biggerDigit]),
)
if sumValues(factorsAfterReplacement) <= spaceAfterThisDigit {
fillOnes := spaceAfterThisDigit - sumValues(factorsAfterReplacement)
return num[:i] + strconv.Itoa(biggerDigit) + strings.Repeat("1", fillOnes) + construct(factorsAfterReplacement)
}
}
}
factorsAfterExtension := getFactorCount(primeCount)
return strings.Repeat("1", len(num)+1-sumValues(factorsAfterExtension)) + construct(factorsAfterExtension)
}
var kFactorCounts = map[int]map[int]int{
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},
}
func getPrimeCount(t int64) (map[int]int, bool) {
count := map[int]int{2: 0, 3: 0, 5: 0, 7: 0}
for _, prime := range []int{2, 3, 5, 7} {
for t%int64(prime) == 0 {
t /= int64(prime)
count[prime]++
}
}
return count, t == 1
}
func getPrimeCountFromString(num string) map[int]int {
count := map[int]int{2: 0, 3: 0, 5: 0, 7: 0}
for _, d := range num {
for prime, freq := range kFactorCounts[int(d-'0')] {
count[prime] += freq
}
}
return count
}
func getFactorCount(count map[int]int) map[int]int {
res := map[int]int{}
count8 := count[2] / 3
remaining2 := count[2] % 3
count9 := count[3] / 2
count3 := count[3] % 2
count4 := remaining2 / 2
count2 := remaining2 % 2
count6 := 0
if count2 == 1 && count3 == 1 {
count2, count3 = 0, 0
count6 = 1
}
if count3 == 1 && count4 == 1 {
count2 = 1
count6 = 1
count3, count4 = 0, 0
}
res[2] = count2
res[3] = count3
res[4] = count4
res[5] = count[5]
res[6] = count6
res[7] = count[7]
res[8] = count8
res[9] = count9
return res
}
func construct(factors map[int]int) string {
var res strings.Builder
for digit := 2; digit < 10; digit++ {
res.WriteString(strings.Repeat(strconv.Itoa(digit), factors[digit]))
}
return res.String()
}
func isSubset(a, b map[int]int) bool {
for key, value := range a {
if b[key] < value {
return false
}
}
return true
}
func subtract(a, b map[int]int) map[int]int {
res := make(map[int]int, len(a))
for k, v := range a {
res[k] = v
}
for k, v := range b {
res[k] = max(0, res[k]-v)
}
return res
}
func sumValues(count map[int]int) int {
sum := 0
for _, v := range count {
sum += v
}
return sum
}