Số nguyên nhỏ nhất chia hết cho K trong Python

Giả sử có số nguyên dương K, ta cần tìm số nguyên dương nhỏ nhất N sao cho N chia hết cho K, và N chỉ chứa chữ số 1. Ta phải tìm độ dài của N. Nếu không có N như vậy, trả về -1. Nếu đầu vào 3, kết quả 3. N nhỏ nhất là N = 111.

Để giải quyết, ta làm theo các bước −

• nếu k chẵn hoặc k chia hết cho 5, trả về -1
• gán r := 0 và N = 1
• với i từ 1 đến K+1
  • r := (r * 10 + 1) mod k
  • nếu r = 0, trả về i

Xem triển khai sau −

Ví dụ

class Solution(object):    def smallestRepunitDivByK(self, K):       if K%2==0 or K%5 ==0:          return -1       r = 0       N=1       for i in range(1,K+1):          r = (r*10 + 1)%K          if r == 0:             return i ob = Solution() print(ob.smallestRepunitDivByK(11))

Đầu vào

11

Kết quả

2