LeetCode Entry

1015. Smallest Integer Divisible by K

25.11.2025 medium 2025 kotlin rust

Smallest number 11..1 % k

1015. Smallest Integer Divisible by K medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1184

Problem TLDR

Smallest number 11..1 % k #medium

Intuition

    // k 10^5
    // x*k = n, n is '1(1)`
    // return length(n) or lg(n)
    // smallest
    // 11 = 10 + 1
    // 111 / 3 = 37
    // this is math brainteaser
    //
    // what numbers gives 1 at the end
    // 1 7 11
    //
    // how to make result all of ones?
    //
    // or, if we take long string of ones how to find if it is %k
    // we have to multiply by 10 and add 1
    // can we do %k every time and check first that is 0?
    // how to stop?

Approach

• to stop look for remainder loops or just stop at k steps

Complexity

• Time complexity: \(O(k)\)

• Space complexity: \(O(1)\)

Code

// 11ms
    fun smallestRepunitDivByK(k: Int): Int {
        var x = 0
        return (1..k).firstOrNull { x = (x * 10 + 1) % k; x == 0 } ?: -1
    }

// 0ms
    pub fn smallest_repunit_div_by_k(k: i32) -> i32 {
        let mut x = 0;
        (1..=k).find(|i| {x=(x*10+1)%k; x==0}).unwrap_or(-1)
    }