[leetcode]Smallest Integer Divisible by K

하.. 정말 많은 일이 있었다. 한달이 어떻게 흘러갔는질 모르겠다. 누가 날 물에 담궜다가 뺀 기분일정도로 진짜 정신없이 갔다. 이는 나중에 여유가 생기면 포스팅을 하고.. 오늘은 가볍게 다시 리셋된 뇌를 깨우기 위해 오랜만에 leetcode를 접속해서 문제를 풀었다.

역시 한달은 내 뇌가 클린해지기 충분하고도 남은 시간이였다. 이제 다시 매일 꾸준히 풀기위해 노력해야겠다. 😌

 

leetcode.com/problems/smallest-integer-divisible-by-k/submissions/

Smallest Integer Divisible by K - LeetCode

 

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.

 

leetcode는 항상 처음에 문제를 이해하기가 조금 난해한게 없지않아 있다. 그냥 내가 영어를 못하는건ㄱㅏ..

주어진 k로 나눌 수 있는 1로만 구성되어있는 최소 정수의 길이를 구하는 문제였다.

 

처음엔 아래와 같이 풀었으나 시간초과가 났다. 

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        rem = 0
        for i in range(1, K+1): #k가 3이 들어오면 1부터 3까지 올라가면서
            rem = int("1"*i) % K 
            if rem == 0:
                return i
        return -1

 

풀이를 봤다. rem*10+1 부분이 인상적이였다. 앞에 남은 값에 뒤에 1을 추가해서 전체적으로 1로 구성된 값을 나누는 식으로 값을 세팅할 수 있었다.

class Solution:
    def smallestRepunitDivByK(self, K: int) -> int:
        rem = 0
        for i in range(1,K+1):
            rem = (rem*10+1)%K
            if rem == 0:
                return i
        return -1