Smallest Divisible Digit Product II solution and explanation
Google
The problem
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
Approach overview
Problem Overview: Given a numeric string and a target value t, you must construct the smallest number greater than or equal to the input such that the product of its digits is divisible by t. The number must be built using digits 0–9 while preserving the smallest possible lexicographic value.
Approach 1: Increment and Check (Brute Force) (Time: O(k * d), Space: O(1))
The straightforward method repeatedly increments the current number and checks whether the product of its digits is divisible by t. Convert the number to digits, multiply them, and verify product % t == 0. This approach works because every candidate is tested directly. However, when the input length grows, the number of increments can explode, especially if the valid answer is far away. The digit product calculation costs O(d) per check where d is the number of digits, making the method impractical for large constraints. Still, it provides a correctness baseline and helps validate optimized solutions.
Approach 2: Backtracking with Greedy Digit Construction (Time: O(9^d) worst case, heavily pruned; Space: O(d))
A more practical strategy builds the result digit by digit using backtracking. First factorize t using number theory insights and track what prime factors the final digit product must contain. While constructing the number, try digits from smallest to largest to keep the result minimal. Each chosen digit contributes factors to the cumulative product. If the remaining positions cannot satisfy the remaining factor requirements, prune the branch immediately. This pruning drastically reduces the search space. The algorithm effectively combines greedy ordering with recursive exploration so that the first valid completion is already the smallest valid number.
The implementation usually processes the number as a string, allowing easy digit replacement and prefix comparison with the original input. Once a prefix exceeds the original number, the remaining digits can be filled greedily with the smallest digits that satisfy the remaining factor constraints.
Recommended for interviews: Start by explaining the increment-and-check baseline to demonstrate problem understanding. Then move to the backtracking + factor tracking approach. Interviewers expect you to reduce the brute-force search space using pruning, greedy ordering, and factor decomposition.
Approach 1: Increment and Check
In this approach, we start from the given number and systematically try to find the smallest zero-free number whose digits' product is divisible by t. We will increment the number and check whether it satisfies the required conditions, replacing any '0' digits with '1' if they appear, since zero-free condition must be maintained.
def is_product_divisible(num, t):
product = 1
for digit in num:
digit = int(digit)
if digit == 0:
return False
product *= digit
product %= t
return product % t == 0
def increment(num):
number = list(num)
i = len(number) - 1
while i >= 0:
if number[i] < '9':
number[i] = chr(ord(number[i]) + 1)
return ''.join(number)
number[i] = '1'
i -= 1
return '1' + ''.join(number)
def smallest_divisible(num, t):
attempts = 0
while not is_product_divisible(num, t) or '0' in num:
num = increment(num)
attempts += 1
if attempts > 100000:
return "-1"
return num
print(smallest_divisible("1234", 256))import java.math.BigInteger;
public class SmallestDivisible {
private static boolean isProductDivisible(String num, long t) {
long product = 1;
for (char c : num.toCharArray()) {
int digit = c - '0';
if (digit == 0)
return false;
product *= digit;
if (product > t) {
product %= t;
}
}
return product % t == 0;
}
private static boolean isZeroFree(String num) {
return !num.contains("0");
}
private static String increment(String num) {
BigInteger number = new BigInteger(num);
number = number.add(BigInteger.ONE);
return number.toString().replace('0', '1');
}
public static String smallestDivisible(String num, long t) {
int attempts = 0;
while (!isProductDivisible(num, t) || !isZeroFree(num)) {
num = increment(num);
if (++attempts > 100000) {
return "-1";
}
}
return num;
}
public static void main(String[] args) {
String num = "1234";
long t = 256;
System.out.println(smallestDivisible(num, t));
}
}#include <iostream>
#include <string>
using namespace std;
bool isProductDivisible(const string& num, long long t) {
long long product = 1;
for (char c : num) {
int digit = c - '0';
if (digit == 0)
return false;
product *= digit;
if (product > t) {
product %= t;
}
}
return product % t == 0;
}
bool isZeroFree(const string& num) {
return num.find('0') == string::npos;
}
void increment(string& num) {
int i = num.length() - 1;
while (i >= 0) {
if (num[i] < '9') {
num[i]++;
break;
}
num[i] = '1'; // avoid zero
i--;
}
if (i < 0) {
num = '1' + num;
}
}
string smallestDivisible(string num, long long t) {
int attempts = 0;
while (!isProductDivisible(num, t) || !isZeroFree(num)) {
increment(num);
if (++attempts > 100000) {
return "-1";
}
}
return num;
}
int main() {
string num = "1234";
long long t = 256;
cout << smallestDivisible(num, t) << endl;
return 0;
}function isProductDivisible(num, t) {
let product = 1;
for (let digit of num) {
digit = Number(digit);
if (digit === 0) return false;
product *= digit;
product %= t;
}
return product % t === 0;
}
function increment(num) {
let number = num.split('').map(Number);
let i = number.length - 1;
while (i >= 0) {
if (number[i] < 9) {
number[i] += 1;
for (let j = i + 1; j < number.length; j++) {
number[j] = 1;
}
break;
}
number[i] = 1;
i -= 1;
}
if (i < 0) {
number.unshift(1);
}
return number.join('');
}
function smallestDivisible(num, t) {
let attempts = 0;
while (!isProductDivisible(num, t) || num.includes('0')) {
num = increment(num);
if (++attempts > 100000) {
return "-1";
}
}
return num;
}
console.log(smallestDivisible("1234", 256));#include <stdio.h>
#include <string.h>
int isProductDivisible(char *num, long long t) {
long long product = 1;
for (int i = 0; num[i]; i++) {
int digit = num[i] - '0';
if (digit == 0)
return 0;
product *= digit;
if (product > t) {
product %= t;
}
}
return product % t == 0;
}
int isZeroFree(char *num) {
for (int i = 0; num[i]; i++) {
if (num[i] == '0') return 0;
}
return 1;
}
void increment(char *num) {
int len = strlen(num);
int i = len - 1;
while (i >= 0) {
if (num[i] < '9') {
num[i]++;
break;
}
num[i] = '1'; // avoid zero
i--;
}
if (i < 0) {
memmove(num + 1, num, len + 1);
num[0] = '1';
}
}
void smallestDivisible(char *num, long long t, char *result) {
int attempts = 0;
while (!isProductDivisible(num, t) || !isZeroFree(num)) {
increment(num);
if (++attempts > 100000) {
strcpy(result, "-1");
return;
}
}
strcpy(result, num);
}
int main() {
char num[] = "1234";
long long t = 256;
char result[256];
smallestDivisible(num, t, result);
printf("%s\n", result);
return 0;
}using System;
using System.Numerics;
class SmallestDivisibleDigitProduct
{
static bool IsProductDivisible(string num, long t)
{
long product = 1;
foreach (char c in num)
{
int digit = c - '0';
if (digit == 0)
return false;
product *= digit;
if (product > t)
{
product %= t;
}
}
return product % t == 0;
}
static string Increment(string num)
{
BigInteger number = BigInteger.Parse(num);
number++;
return number.ToString().Replace('0', '1');
}
static string SmallestDivisible(string num, long t)
{
int attempts = 0;
while (!IsProductDivisible(num, t) || num.Contains('0'))
{
num = Increment(num);
if (++attempts > 100000)
{
return "-1";
}
}
return num;
}
static void Main()
{
string num = "1234";
long t = 256;
Console.WriteLine(SmallestDivisible(num, t));
}
}In this Python implementation, we define functions to validate if a number's digits multiply to something divisible by t. A helper function ensures all numbers are incremented to be zero-free.
Time Complexity: O(digit count × iteration limit).
Space Complexity: O(n), where n is the length of the number string.
Approach 2: Backtracking Approach
In this approach, we employ backtracking to generate candidate numbers meeting the requirements. By systematically building numbers through potential digits, we ensure the resulting number is zero-free and checks the product divisibility. Unlike incremental changes, this method prevents excessive retries by pruning paths failing early tests.
def backtrack(number, idx, product, t):
if idx == len(number):
return ''.join(map(str, number)) if product % t == 0 else None
for digit in range(1, 10):
number[idx] = digit
result = backtrack(number, idx + 1, product * digit, t)
if result:
return result
return None
def smallest_divisible_backtrack(num_str, t):
number = [int(x) for x in num_str]
result = backtrack(number, 0, 1, t)
return result if result else "-1"
print(smallest_divisible_backtrack("1234", 256))This Python backtracking solution recursively explores altering digits in the given number. The approach integrates pruning based on immediate product divisibility signals, constructing the smallest potential zero-free number one digit at a time.
Time Complexity: Potentially exponential due to exhaustive search but pruned early.
Space Complexity: O(n), for maintaining current number and function call stack.
Approach 3: Default Approach
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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Increment and Check | Time Complexity: O(digit count × iteration limit). |
| Backtracking Approach | Time Complexity: Potentially exponential due to exhaustive search but pruned early. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Increment and Check | O(k * d) | O(1) | Baseline or brute-force validation when constraints are very small |
| Backtracking with Greedy Digit Selection | O(9^d) worst case with strong pruning | O(d) | General solution for large inputs where pruning based on remaining factors drastically reduces search |
Frequently asked questions
Is Smallest Divisible Digit Product II easy or hard?
Smallest Divisible Digit Product II is classified as Hard because it combines multiple concepts: digit manipulation, number theory, greedy ordering, and backtracking with pruning. Efficiently reducing the search space is the main challenge.
Smallest Divisible Digit Product II Python/Java solution
Python and Java implementations usually follow the same structure: factorize t, iterate through digits in increasing order, and recursively build the number while maintaining the remaining factor requirements. Python solutions often use recursion and dictionaries, while Java implementations rely on arrays and helper methods for factor tracking.
How to solve Smallest Divisible Digit Product II in O(n)?
A strict O(n) solution is generally not feasible because the algorithm may need to explore multiple digit combinations. Instead, efficient solutions rely on greedy ordering and backtracking with pruning. Factorizing t and tracking remaining prime factors allows the search to skip large portions of the candidate space.
What is the best approach for Smallest Divisible Digit Product II?
The most effective solution uses backtracking combined with greedy digit selection. Factorize the target t and track which prime factors must still appear in the digit product. While constructing the number digit by digit, prune branches that cannot satisfy the remaining factor requirements. This ensures the first valid result is the smallest possible number.
Is Smallest Divisible Digit Product II asked at Google/Amazon/Meta?
Problems involving digit construction, factorization, and constrained search frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that combine number theory with backtracking are especially common in senior-level algorithm rounds.
What data structure is used in Smallest Divisible Digit Product II?
The core implementation typically uses strings or arrays to manipulate digits, along with recursion for backtracking. A map or array may track remaining prime factors of t. These structures make it easy to update the digit product contribution while exploring candidate numbers.
What is the time complexity of Smallest Divisible Digit Product II?
The brute-force increment-and-check approach can take O(k * d) time where k is the number of increments attempted and d is the number of digits. The optimized backtracking solution has a worst-case search of O(9^d), but aggressive pruning based on remaining factor requirements dramatically reduces the actual runtime.