[Rust] Not optimal, but reasoned this one out
From other posts, I see that it turns out that "if a number is not divisible by 2 or 5, then it is a divisor of some repunit". Knowing this you can optimize my 
From other posts, I see that it turns out that "if a number is not divisible by 2 or 5, then it is a divisor of some repunit". Knowing this you can optimize my solution quite a bit, but this was fun anyway.\n\nSince I didn\'t know the above, what I noticed is that I can write a repunit as follows.\n\n```\nn = 10^(i -1) + 10^(i - 2) + ... + 10 + 1\n```\n\nNow if I use Euclid\'s algorithm on `n` to divide by some number `k` I get \n\n```\nn = (q_(i - 1) * k + r_(i - 1)) + ... + (q_1 * k + r_1) + (q_0 * k + r_0)\n```\n\nNow we see that if `k` divides the sum of the `r_i` then `k` divides `n`, which is the same as saying\nthe sum is 0 mod k.\n\nNow the algoirhtm I came up with is to compute `r_i` sequentually, and sum them up mod k. If this is zero, return\nthe number of `r_i` that I computed. However, if we every see a sum of `r_i` repeat, then it\'s sort of like long division where we have a repeating pattern, so we can safely reason that we will never find a sum that is 0 mod k.\n\nLastly, we have to ensure that we will always either run into a 0 or a repeating pattern. We can guarantee that since we are doing this math mod k, and so there are only a finite number of sums mod k that we can compute. Thus pidgenhole principle says if we don\'t find a zero, we will find a repeat.\n\n```rust\nuse std::collections::HashSet;\n\npub struct Solution {}\n\nimpl Solution {\n  pub fn smallest_repunit_div_by_k(k: i32) -> i32 {\n    let mut seen = HashSet::new();\n    let mut n = 1;\n    let mut r = 1 % k;\n    let mut sum = r;\n    loop {\n      if sum == 0 {\n        return n;\n      } else if seen.contains(&sum) {\n        return -1;\n      }\n      seen.insert(sum);\n      r = (10 * r) % k;\n      sum = (sum + r) % k;\n      n += 1;\n    }\n  }\n}\n```
[]