LeetCode Entry

3345. Smallest Divisible Digit Product I

06.08.2026 easy 2026 kotlin rust

Smallest n.. digits product divisible by t

3345. Smallest Divisible Digit Product I easy substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1443

Problem TLDR

Smallest n.. digits product divisible by t

Intuition

Brute force n..inf.

Approach

• any zero in the number gives the satisfied result 0%t==0
• to go top-down from t to 1 we can remove each digit contribution by dividing by it’s gcd(t,d)

Complexity

• Time complexity: \(O(log^2(n))\)

• Space complexity: \(O(log(n))\)

Code

    fun smallestNumber(n: Int, t: Int) =
    (n..n+9).find{"$it".fold(1){a,b->a*(b-'0')}%t<1}

    pub fn smallest_number(n: i32, t: i32) -> i32 {
       (n..n+10).find(|x|x.to_string().bytes().fold(1,|r,t|r*(t-b'0')as i32)%t<1).unwrap()
    }