[leetcode #1015] Smallest Integer Divisible by K

Problem

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.

Example 1:

Input: k = 1
Output: 1
Explanation: The smallest answer is n = 1, which has length 1.

Example 2:

Input: k = 2
Output: -1
Explanation: There is no such positive integer n divisible by 2.

Example 3:

Input: k = 3
Output: 3
Explanation: The smallest answer is n = 111, which has length 3.

Constraints:

・ 1 <= k <= 10⁵

Idea

모든 자리수가 1로 된 수 중 k로 나뉘어지는 최소값의 길이가 몇인지 구하는 문제다.

30분 정도 생각하고 풀리지 않아 Solution을 봤다. =_=

Solution을 보니 대학교 때 잠깐 배웠던 비둘기집 원리 (https://en.wikipedia.org/wiki/Pigeonhole_principle)가 등장했다.

알고리즘은 간단한데, N = N * 10 + 1을 사용해 1로만 이루어진 수를 하나하나씩 k로 나뉘어지는지 확인한다.

이 때 유의해야 할 점은 N이 64-bit integer 범위를 넘을 수 있으므로 나머지를 사용해야 한다는 것이다. N = remainder * 10 + 1을 반복해서 계산하면 되고 반복횟수를 제한하지 않으면 무한루프에 빠지게 되므로, 비둘기집 원리를 사용해야 한다. 비둘기집 원리에 따르면 K번 반복해서 나뉘어지지 않을 때 더 이상 반복할 필요가 없다.

나뉘어지는 것이 확인되면 루프를 반복할 때마다 increment시킨 값을 N의 길이로 리턴하면 되고, 루프를 빠져나오게 되면 -1을 리턴한다.

Solution

class Solution {
    public int smallestRepunitDivByK(int k) {
        int remainder = 0;
        int length = 1;

        for (int i=0; i < k; i++) {
            int n = remainder * 10 + 1;
            remainder = n % k;
            if (remainder == 0) {
                return length;
            }
            length++;
        }

        return -1;
    }
}

Reference

https://leetcode.com/problems/smallest-integer-divisible-by-k/