Find the Smallest Zero-Free Number with a Divisible Digit Product

# Find the Smallest Zero-Free Number with a Divisible Digit Product ### Problem You are given a decimal string `num` representing a positive integer, and a positive integer `t`. Return a decimal string representing the smallest number that: - Is greater than or equal to `num` numerically. - Contains no zero digit. - Has a digit product divisible by `t`. If no such number exists, return `"-1"`. The result may have more digits than `num`. The allowed input length can exceed the capacity of fixed-width integer types. ### C++ Interface ```cpp class Solution { public: string smallestNumber(string num, long long t); }; ``` ### Examples #### Example 1 **Input:** `num = "109", t = 6` **Output:** `"116"` **Explanation:** `109` and `110` contain zero. The digit products for `111` through `115` are `1` through `5`, none divisible by `6`. The product for `116` is `6`, so it is the smallest qualifying number. #### Example 2 **Input:** `num = "88", t = 11` **Output:** `"-1"` **Explanation:** A product of digits from `1` through `9` cannot contain the prime factor `11`, so no zero-free number can qualify. ### Constraints - `2 <= num.size() <= 200000` - `num` contains only decimal digits and has no leading zero. - `1 <= t <= 10^14` ### Clarifying Questions - Can `num` contain zero? Yes; the returned number cannot. - Is a product equal to `t` required? No, any product divisible by `t` is valid. - Can the unchanged input be returned? Yes, if it is zero-free and its digit product qualifies. - Are leading zeros allowed in the result? No, all result digits must lie in `1` through `9`. ### What a Strong Answer Covers - Establishes when a solution exists under the zero-free condition. - Justifies numerical minimality, including unchanged inputs, an increased digit, and a longer result when needed. - Handles very long strings and large products without integer overflow. - Gives time and space bounds that support the full constraints. ### Follow-up Questions - Why does allowing zero digits change the existence question? - How can unused digit positions be filled without changing product divisibility? ```hint Represent divisibility without forming the product Every nonzero decimal digit factors using only a small set of primes. Track the remaining required exponents rather than multiplying the digits. ``` ```hint Decide whether a suffix can fit For a fixed prefix, ask for the fewest additional digits needed to supply the missing factors. Extra positions can use digit one. This can test possible first changes to the original number. ```