3345. Smallest Divisible Digit Product I · Interview Problem

Back to problems

Leetcode

Easy

Math

Number Theory

Arrays

3345. Smallest Divisible Digit Product I

Find the smallest integer greater than or equal to a given number whose digit product is divisible by a target value.

Acceptance 0%

Start Practice

Problem Statement

Given two integers $n$ and $t$ , find the smallest integer $x$ such that $x \ge n$ and the product of the digits of $x$ is divisible by $t$ .

You may assume the answer always exists within the search range used by the original problem.

Input Format

Two integers $n$ and $t$ .
Digits of a number are the decimal digits in its standard representation.

Output Format

Return the smallest integer $x \ge n$ whose digit product is divisible by $t$ .

Constraints

$1 \le n$
$1 \le t$
The answer is guaranteed to exist for the intended input range.

Examples

Sample cases returned by the problem API.

Example 1

Input

n = 10, t = 2

Output

Explanation

The digit product of 10 is 1 \u00d7 0 = 0, and 0 is divisible by 2. Since 10 is already valid, it is the smallest answer.

Example 2

Input

n = 17, t = 5

Output

Explanation

17 has digit product 7, which is not divisible by 5. 18, 19, 20, 21, 22, 23, and 24 also fail. For 25, the digit product is 2 \u00d7 5 = 10, which is divisible by 5.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress