Smallest Divisible Digit Product II - Practice Coding Problems

Smallest Divisible Digit Product II - Problem

Math String Backtracking Greedy Number Theory Hard

You're given a string num representing a positive integer and an integer t. Your mission is to find the smallest zero-free number that is greater than or equal to num and has a special property: the product of its digits must be divisible by t.

A number is zero-free if none of its digits are 0. This constraint makes the problem particularly challenging since we can't use 0 as a "filler" digit.

Goal: Return a string representing this magical number, or "-1" if no such number exists.

Example: If num = "1234" and t = 6, we need to find the smallest number ≥ 1234 with no zeros where digit product is divisible by 6. The digit product of 1234 is 1×2×3×4 = 24, and 24 ÷ 6 = 4, so "1234" itself works!

Input & Output

example_1.py — Basic Case

$ Input: num = "1234", t = 6

› Output: "1234"

💡 Note: The digit product of 1234 is 1×2×3×4 = 24, and 24 is divisible by 6 (24 ÷ 6 = 4). Since 1234 ≥ 1234 and contains no zeros, it's our answer.

example_2.py — Need to Increment

$ Input: num = "1000", t = 10

› Output: "1125"

💡 Note: 1000 contains zeros, so we need to find a larger zero-free number. We need digit product divisible by 10 = 2×5. The number 1125 has product 1×1×2×5 = 10, which is divisible by 10.

example_3.py — Impossible Case

$ Input: num = "1", t = 11

› Output: "-1"

💡 Note: Since 11 is prime and greater than 7, and digits can only contribute prime factors 2, 3, 5, 7, it's impossible to create a digit product divisible by 11.

Constraints

1 ≤ num.length ≤ 10⁵
num consists of only digits and does not have leading zeros
1 ≤ t ≤ 10⁹
The result number should not exceed reasonable length limits

Visualization

Tap to expand

Understanding the Visualization

Factor Analysis

Break t = 60 into prime factors: 2² × 3 × 5

Digit Mapping

Map each digit to its prime factors: 6 = 2×3, 4 = 2², etc.

Greedy Assignment

Try to use the smallest digits that provide the required factors

Validation

Ensure the result is ≥ input number and zero-free

Key Takeaway

🎯 Key Insight: Only prime factors 2, 3, 5, 7 can be formed from digits 1-9. Use backtracking to distribute these factors optimally across digit positions, building the smallest valid number systematically.

Asked in

G Google 45 a Amazon 38 f Meta 32 ⊞ Microsoft 28

The optimal approach uses backtracking with prime factorization. Key insight: since digits 1-9 can only contribute prime factors 2, 3, 5, and 7, we first check if t can be formed using only these primes. Then we use backtracking to construct the number digit by digit, tracking remaining prime factors needed and pruning impossible branches. This avoids the exponential search space of brute force.

Common Approaches

Approach	Time	Space	Notes
✓ Backtracking with Digit Construction	O(9^d)	O(d)	Build the number digit by digit using backtracking and pruning
Brute Force (Try Every Number)	O(k * d)	O(1)	Increment from the given number and check each candidate

Backtracking with Digit Construction — Algorithm Steps

Factorize t into prime factors (2, 3, 5, 7 only, since digits 1-9 can only contribute these)
Use backtracking to place digits from left to right
For each position, try digits 1-9 and track remaining factors needed
Prune branches where remaining factors cannot be satisfied by remaining positions
When we have a complete number, verify it's >= original number

Visualization

Tap to expand

Step-by-Step Walkthrough

Factorize target t

Break t into prime factors 2, 3, 5, 7

Try digits at each position

For each position, try digits 1-9

Track remaining factors

Update remaining factors needed after placing each digit

Prune impossible branches

Skip branches where remaining factors cannot be satisfied

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int digitFactors[10][4]; // [digit][prime_index] where primes are [2,3,5,7]
int targetFactors[4];

bool canForm(int n) {
    int primes[] = {2, 3, 5, 7};
    for (int i = 0; i < 4; i++) {
        while (n % primes[i] == 0) {
            n /= primes[i];
        }
    }
    return n == 1;
}

void initializeDigitFactors() {
    int factors[9][4] = {{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}};
    for (int i = 1; i <= 9; i++) {
        for (int j = 0; j < 4; j++) {
            digitFactors[i][j] = factors[i-1][j];
        }
    }
}

void getPrimeFactors(int n) {
    int primes[] = {2, 3, 5, 7};
    for (int i = 0; i < 4; i++) {
        targetFactors[i] = 0;
        while (n % primes[i] == 0) {
            targetFactors[i]++;
            n /= primes[i];
        }
    }
}

char* backtrack(int pos, char* currentNum, int* remainingFactors, 
               bool isSmaller, const char* num, int len) {
    if (pos == len) {
        bool valid = true;
        for (int i = 0; i < 4; i++) {
            if (remainingFactors[i] > 0) {
                valid = false;
                break;
            }
        }
        if (valid) {
            char* result = malloc(len + 1);
            strcpy(result, currentNum);
            return result;
        }
        return NULL;
    }
    
    int start = 1;
    if (!isSmaller && pos < strlen(num)) {
        start = num[pos] - '0';
    }
    
    for (int digit = start; digit <= 9; digit++) {
        int newRemaining[4];
        for (int i = 0; i < 4; i++) {
            newRemaining[i] = remainingFactors[i] - digitFactors[digit][i];
        }
        
        currentNum[pos] = '0' + digit;
        bool newIsSmaller = isSmaller || (pos < strlen(num) && digit > (num[pos] - '0'));
        
        char* result = backtrack(pos + 1, currentNum, newRemaining, newIsSmaller, num, len);
        if (result) {
            return result;
        }
    }
    
    return NULL;
}

char* smallestNumber(const char* num, int t) {
    if (!canForm(t)) {
        char* result = malloc(3);
        strcpy(result, "-1");
        return result;
    }
    
    initializeDigitFactors();
    getPrimeFactors(t);
    
    int len = strlen(num);
    char* currentNum = malloc(len + 2);
    memset(currentNum, '0', len + 1);
    currentNum[len + 1] = '\0';
    
    char* result = backtrack(0, currentNum, targetFactors, false, num, len);
    if (result && atoll(result) >= atoll(num)) {
        free(currentNum);
        return result;
    }
    if (result) free(result);
    
    memset(currentNum, '0', len + 1);
    result = backtrack(0, currentNum, targetFactors, true, num, len + 1);
    free(currentNum);
    
    if (result) {
        return result;
    }
    
    char* failResult = malloc(3);
    strcpy(failResult, "-1");
    return failResult;
}

int main() {
    char num[20];
    int t;
    scanf("%s %d", num, &t);
    char* result = smallestNumber(num, t);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(9^d)

d is number of digits, but heavy pruning reduces this significantly in practice

✓ Linear Growth

Space Complexity

O(d)

Recursion depth is at most the number of digits

✓ Linear Space

28.4K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Backtracking with Digit Construction — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler