Daily classic

Xin Qiji (Song) “Eternal Happiness: Jingkou North Guting Nostalgic for the Past”

Through the ages, the hero did not find, Sun Zhongmou. Dance pavilion song Tai, wind is always, rain wind blowing. Setting sun grass trees, ordinary alleys, human slaves have lived. Think that year, iron horse, swallow ten thousand miles such as tiger.

Yuan Jia caocao, feng Wolf Ju Xu, won scanghuang north gu. Forty-three years, wang Zhong still remember, beacon Yangzhou road. Can look back, Buddha fox temple, a god crow society drum. Who asks: lian Po old, still can feed?

describe

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.
Copy the code

Example 2:

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

Example 3:

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

Note:

1 <= k <= 10^5
Copy the code

parsing

Given a positive integer k, we need to find the smallest positive integer n, such that n is divisible by k and contains only the number 1, returning the length of n. If there is no such n, -1 is returned.

After reading the problem, we actually realized that this was a problem to find a pattern, so let’s just arbitrarily pick k = 3 and give a couple of examples

1%3=1 1*10+1=11%3=2 11*10+1=111%3=0 111*10+1=1111%3=1 1111*10+1=11111%3=2 11111*10+1=111111%3=0Copy the code

We find that there is a rule in modulo k=3, for example, 11 modulo 3 is the modulo result of 1 modulo 3 times 10 and then add the value of 1 modulo 3, and so on, 111 modulo 3, It’s 11 modulo 3 times 10 and then plus 1 modulo 3, and by doing that, then we can figure out the modulo k of a positive integer with n digits of 1, and then we can store the modulo k in a set, and if the modulo is 0, that means it’s divisible, Return n directly; If the result of modulo is already present in the set, it means that the modulo of k will be repeated even if it is composed of many positive integers of 1, and no result will be returned.

In addition, the following code was added at the beginning to say that the speed could be increased, but I didn’t understand why, and the actual operation effect found that the speed did not increase, but the time was 8 ms more:

if k % 10 not in {1, 3, 7, 9}: return -1
Copy the code

answer

class Solution(object):
    def smallestRepunitDivByK(self, k):
        """
        :type k: int
        :rtype: int
        """
        mod = 0
        mods = set()
        for n in range(1, k+1):
            mod = (mod * 10 + 1) % k
            if mod==0:
                return n
            if mod in mods:
                return -1
            mods.add(mod)
        return -1
        	      
		
Copy the code

The results

Each node in the Python online submission list has a range of views for each node. 18 MB, less than 14.29% of Python online submissions for Smallest Integer Divisible by K.Copy the code

Original link: leetcode.com/problems/sm…

Your support is my biggest motivation