LeetCode 2020-11-25: Smallest Integer Divisible by K

Smallest Integer Divisible by K (medium) の挑戦メモです。

問題の概要

• 1, 11, 111 といった 1 が連なった数値を K で除算して余りなしで割り切ったときの 111... の数値の長さ (最小のやつ) を求める
  • どの数値も与えられた K では割り切れない場合は、-1 を答えとする

考え方

• ナイーブに 1 を連ねた数値を作って剰余を求める、みたいなことをするとちょっと時間的にも空間的にも辛いことになりそうだ 🤔
  • 問題的にも 64 ビットの整数で表現できない可能性が示唆されている
  • 定数オーダーの空間計算量で実現する方法を考えねばならないね…
• こういうのはどうだろうか？
  • 1111 みたいな数値を 1000 + 111 と分解し、1000 % K と 111 % K の余りをそれぞれ計算することを考える
    • 1111 % K は、((1000 % K) + (111 % K)) % K で得られるものと同じになるはず
      • 111 % K の部分については再帰的に 100 % K と 11 % K に分解して考えよう
    • 問題は 1000 % K をどうやって求めるかだけど、これは ((100 % K) * 10) % K を計算することに相当するよね？
      • よって、こちらも再帰的に求めることができそう
  • この分解方法で考えれば、1 % K から始めて次は 11 % K、その次は 111 % K、… というのを二つの int 変数だけで逐次的に計算できそう
• 早速実装してみて submit → ああっ！ time limit exceeded になってしまった 🤮
  • 無限ループが発生してしまったわけだけど、これは K が偶数の場合を除去していないからか…
    • 1 が連なる数値は奇数なので、K が偶数だとどんな値でも割り切ることはできない…
• 偶数の K を弾くように修正して submit してみたが、また time limit exceeded を喰らってしまった 😭
  • なるほど、K が 5 の倍数のときも同様に割り切れませんね…
• K が 2 or 5 の倍数である場合を弾くようにして submit → 今度こそ accept 🤗
  • Runtime 1ms で 100% beats 達成 💪
• なお accept してから hint を見てみたけど、なんともっと簡単な解法があったんですね…… 💦

コード

class Solution {
    public int smallestRepunitDivByK(int K) {
        // 2 の倍数と 5 の倍数は必ず -1 になる
        if ((K & 1) == 0 || K % 5 == 0) {
            return -1;
        }

        int r1 = 0, r2 = 1;
        int len = 1;
        while ((r1 = (r1 + r2) % K) > 0) {
            r2 = r2 * 10 % K;
            len++;
        }

        return len;
    }
}