Smallest integer divisible by k

Hash Table Math

54.3% acceptance

Feb 25, 2026

1633

1165

Given a positive integer k, you need to find the length of the smallest positive integer n such that n is divisible by k, and n only contains the digit 1. Return the length of n. If there is no such n, return -1. Note: n may not fit in a 64-bit signed integer.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn smallest_repunit_div_by_k(k: i32) -> i32 {
    if k % 2 == 0 || k % 5 == 0 { return -1; }
    let mut r = 0;
    for len in 1..=k {
      r = (r * 10 + 1) % k;
      if r == 0 { return len; }
    }
    -1
  }
}