We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Smallest Divisible Digit Product II

Difficulty: Hard

Problem 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".

Key Insights

  • The number must be zero-free, meaning it cannot contain the digit '0'.
  • The product of the digits of the resulting number must be divisible by t.
  • We need to find the smallest valid number that meets these criteria, which may involve incrementing the input number.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the number string. Space Complexity: O(1), as we use a constant amount of extra space for calculations.

Solution

To solve the problem, we can use a greedy approach:

  1. Start from the given number and check if it is zero-free and if the product of its digits is divisible by t.
  2. If not, increment the number and check again, ensuring that we skip any numbers that contain the digit '0'.
  3. Use a helper function to calculate the product of digits and check divisibility by t.
  4. Continue until a valid number is found or we exhaust possibilities.

Data Structures Used:

  • String to represent the number and manipulate its digits.
  • Integer for calculations.

Algorithmic Approach:

  • Incrementally check each number starting from num.
  • Use a loop to construct new numbers and check their properties.

Code Solutions

def smallest_divisible_digit_product(num: str, t: int) -> str:
    def is_zero_free(s: str) -> bool:
        return '0' not in s

    def product_of_digits(s: str) -> int:
        product = 1
        for digit in s:
            product *= int(digit)
        return product

    num_int = int(num)
    while True:
        current_num = str(num_int)
        if is_zero_free(current_num):
            if product_of_digits(current_num) % t == 0:
                return current_num
        num_int += 1
        if num_int > 10**18:  # Arbitrary limit to avoid infinite loop
            return "-1"
← Back to All Questions