Skip to content

3348. Smallest Divisible Digit Product II

SourceBiweekly Contest 143 Q4DifficultyHardRating3101

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 * 105
  • num consists only of digits in the range ['0', '9'].
  • num does not contain leading zeros.
  • 1 <= t <= 1014

Solutions

Solution 1

Thinking

We need the smallest zero-free integer that is at least \(\textit{num}\) and whose digit product is divisible by \(t\). With \(|\textit{num}| \le 2 \times 10^5\) we cannot increment from \(n\).

If \(t\) has a prime factor other than \(2,3,5,7\), there is no answer. Otherwise we pack the remaining primes into digits \(8,9,6,4\) so the length is minimized.

From the right we try to raise one digit and fill the suffix with ones plus those packed digits; if the current length is too short we prepend ones. That yields the lexicographically smallest valid number.

1


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
 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
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
}

  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
141
142
143
144
145
146
147
impl Solution {
    const DIGIT_PRIME_COUNTS: [[i32; 4]; 10] = [
        [0, 0, 0, 0],
        [0, 0, 0, 0],
        [1, 0, 0, 0],
        [0, 1, 0, 0],
        [2, 0, 0, 0],
        [0, 0, 1, 0],
        [1, 1, 0, 0],
        [0, 0, 0, 1],
        [3, 0, 0, 0],
        [0, 2, 0, 0],
    ];

    pub fn smallest_number(num: String, t: i64) -> String {
        let (required_prime_counts, has_valid_prime_factors) = Self::factorize_target(t);
        if !has_valid_prime_factors {
            return "-1".to_string();
        }
        let required_digit_counts = Self::prime_counts_to_digits(&required_prime_counts);
        if Self::digit_count(&required_digit_counts) > num.len() as i32 {
            let mut result = String::with_capacity(num.len());
            Self::append_digits(&required_digit_counts, &mut result);
            return result;
        }
        let mut prefix_prime_counts = Self::count_primes_in_number(&num);
        let mut first_zero_index = num.find('0');
        if first_zero_index.is_none() {
            first_zero_index = Some(num.len());
            if required_prime_counts
                .iter()
                .zip(prefix_prime_counts.iter())
                .all(|(required, available)| required <= available)
            {
                return num;
            }
        }
        let length = num.len();
        for index in (0..length).rev() {
            let digit = num.as_bytes()[index] - b'0';
            prefix_prime_counts = Self::subtract_counts(
                prefix_prime_counts,
                Self::DIGIT_PRIME_COUNTS[digit as usize],
            );
            let suffix_length = length - 1 - index;
            if index > first_zero_index.unwrap() {
                continue;
            }
            for bigger_digit in digit as i32 + 1..10 {
                let suffix_digit_counts = Self::prime_counts_to_digits(&Self::subtract_counts(
                    Self::subtract_counts(required_prime_counts, prefix_prime_counts),
                    Self::DIGIT_PRIME_COUNTS[bigger_digit as usize],
                ));
                if Self::digit_count(&suffix_digit_counts) <= suffix_length as i32 {
                    let ones_count = suffix_length as i32 - Self::digit_count(&suffix_digit_counts);
                    let mut result = String::with_capacity(length + 1);
                    result.push_str(&num[..index]);
                    result.push((b'0' + bigger_digit as u8) as char);
                    result.extend(std::iter::repeat('1').take(ones_count as usize));
                    Self::append_digits(&suffix_digit_counts, &mut result);
                    return result;
                }
            }
        }
        let extended_digit_counts = Self::prime_counts_to_digits(&required_prime_counts);
        let mut result = String::with_capacity(length + 1);
        result.extend(
            std::iter::repeat('1')
                .take(length + 1 - Self::digit_count(&extended_digit_counts) as usize),
        );
        Self::append_digits(&extended_digit_counts, &mut result);
        result
    }

    fn factorize_target(mut target: i64) -> ([i32; 4], bool) {
        let mut prime_counts = [0; 4];
        for (index, prime) in [2i64, 3, 5, 7].iter().enumerate() {
            while target % prime == 0 {
                target /= prime;
                prime_counts[index] += 1;
            }
        }
        (prime_counts, target == 1)
    }

    fn count_primes_in_number(num: &str) -> [i32; 4] {
        let mut prime_counts = [0; 4];
        for byte in num.bytes() {
            for index in 0..4 {
                prime_counts[index] += Self::DIGIT_PRIME_COUNTS[(byte - b'0') as usize][index];
            }
        }
        prime_counts
    }

    fn prime_counts_to_digits(prime_counts: &[i32; 4]) -> [i32; 10] {
        let count_8 = prime_counts[0] / 3;
        let remaining_2 = prime_counts[0] % 3;
        let count_9 = prime_counts[1] / 2;
        let mut count_3 = prime_counts[1] % 2;
        let mut count_4 = remaining_2 / 2;
        let mut count_2 = remaining_2 % 2;
        let mut count_6 = 0;
        if count_2 == 1 && count_3 == 1 {
            count_2 = 0;
            count_3 = 0;
            count_6 = 1;
        }
        if count_3 == 1 && count_4 == 1 {
            count_2 = 1;
            count_6 = 1;
            count_3 = 0;
            count_4 = 0;
        }
        [
            0,
            0,
            count_2,
            count_3,
            count_4,
            prime_counts[2],
            count_6,
            prime_counts[3],
            count_8,
            count_9,
        ]
    }

    fn append_digits(digit_counts: &[i32; 10], result: &mut String) {
        for digit in 2..10 {
            for _ in 0..digit_counts[digit] {
                result.push((b'0' + digit as u8) as char);
            }
        }
    }

    fn digit_count(digit_counts: &[i32; 10]) -> i32 {
        digit_counts.iter().sum()
    }

    fn subtract_counts(mut counts: [i32; 4], subtrahend: [i32; 4]) -> [i32; 4] {
        for index in 0..4 {
            counts[index] = (counts[index] - subtrahend[index]).max(0);
        }
        counts
    }
}

Comments