[Leetcode] 1015. Smallest Integer Divisible by K

양의 정수 k 가 있다. 모든 자릿수가 1 인 숫자 n 이 있을 때 n / k 의 나머지가 0 이 되는 제일 작은 n 의 자릿수를 반환한다. 만약 값이 없으면 -1을 반환한다.

우선 1의 자리는 1 이 되므로 10의 배수인 모든 k 에 대해 나머지가 나오지 않는 부분을 early return 을 해준다.

모듈로 연산은 덧셈과 곱셈의 경우 보존된다. 다시 말해 (A + B) % k 는 ((A % k) + (B % k)) % k 와 같으며 (A * B) % k 는 ((A % k) * (B % k)) % k 와 같다. Number 자료형은 16자리 까지만 지원하는데 문제의 제약조건은 16자리를 훌쩍 넘기는 n 에 대해서도 성립해야 한다(k 가 10^5 라서 이론상 1 이 10^5 번 붙을 수도 있다). 따라서 커지는 n 을 구하는 것 보다 모듈로 값을 가지고 나머지값만 반복해서 연산을 하면 된다.

비둘기집 원리에 따라 k 번 연산하면 답이 나와야만 하므로 k 번 반복 후 리턴에 걸리지 않았다면 -1 을 반환하도록 만들어서 통과.

function smallestRepunitDivByK(k: number): number {
    if (k % 2 === 0 || k % 5 === 0) {
        return -1;
    }

    let count = 0;
    let remainder = 0;

    for (let i = 0; i < k; i++) {
        count += 1;

        remainder = (remainder * 10 + 1) % k;

        if (remainder === 0) {
            return count;
        }
    }

    return -1
};