MediumNo. 1015
Smallest Integer Divisible by K — LeetCode 1015 Python Solution
- Pattern
- Math and Number Theory
- Topics
- Hash Table, Math
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- k = 1
- Output
- 1
- Explanation
- The smallest answer is n = 1, which has length 1.
Python solution
class Solution:
def smallestRepunitDivByK(self, k: int) -> int:
n = 1 % k
for i in range(1, k + 1):
if n == 0:
return i
n = (n * 10 + 1) % k
return -1Complexity
- Time
- O(k)
- Space · auxiliary
- O(1)where k is the given positive integer
Pattern: Math and Number Theory
Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 1015. Smallest Integer Divisible by K is filed here because LeetCode tags it Math, which is the vocabulary this hub collects.
The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0012 | Integer to Roman | Medium |
| 0013 | Roman to Integer | Easy |
| 0149 | Max Points on a Line | Hard |
| 0166 | Fraction to Recurring Decimal | Medium |
| 0202 | Happy Number | Easy |
| 0264 | Ugly Number II | Medium |
Frequently asked questions
- How hard is LeetCode 1015. Smallest Integer Divisible by K?
LeetCode 1015. Smallest Integer Divisible by K is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1015. Smallest Integer Divisible by K?
The Python solution on this page runs in O(k).
- What is the space complexity of LeetCode 1015. Smallest Integer Divisible by K?
The Python solution on this page uses O(1), where k is the given positive integer auxiliary space.
- What topics does LeetCode 1015. Smallest Integer Divisible by K cover?
LeetCode 1015. Smallest Integer Divisible by K is tagged Hash Table and Math on LeetCode.