โจทย์: หาจำนวนเต็มบวก N ที่เล็กที่สุดที่หาร K ลงตัว และ N ประกอบด้วยตัวเลข 1 เท่านั้น (1, 11, 111, ...) คืนค่าความยาวของ N หาไม่ได้คืน -1
ตัวอย่าง
Input: K = 3
Output: 3 (N = 111)
ข้อสังเกตทางคณิตศาสตร์
- ถ้า K หาร 2 หรือ 5 ลงตัว → ไม่มีคำตอบ (เพราะ 111...1 เป็นเลขคี่และไม่ลงตัว 5)
- ใช้ modulo arithmetic: Nᵢ = (Nᵢ₋₁ × 10 + 1) mod K
- ถ้าเจอ modulo 0 → พบคำตอบ
- ตาม Pigeonhole Principle ต้องเจอภายใน K ขั้นตอน
ตัวอย่างโค้ด Python
class Solution(object):
def smallestRepunitDivByK(self, K):
# กรองกรณีที่ไม่มีคำตอบ
if K % 2 == 0 or K % 5 == 0:
return -1
remainder = 0
for length in range(1, K + 1):
remainder = (remainder * 10 + 1) % K
if remainder == 0:
return length
return -1 # ไม่ควรถึงจุดนี้
# ทดสอบ
ob = Solution()
print(ob.smallestRepunitDivByK(11)) # Output: 2 (11 หาร 11 ลงตัว)
ตัวอย่าง Input/Output
Input: 11 Output: 2
ความซับซ้อน: Time O(K), Space O(1)
