Sponsored
Sponsored
This approach leverages the properties of remainders in modular arithmetic. We try to construct a number which consists of only '1's and is divisible by k. We start with the number 1 and find its remainder with k. Then, iteratively, we add another 1 at the right (equivalent to multiply by 10 and add 1) and find the new remainder. We repeat this process until the remainder becomes 0 or a repetition is detected.
If we encounter a remainder that we have seen before, it indicates a cycle, and there is no such number n that will satisfy the condition, hence return -1.
Time Complexity: O(k), as we check for valid remainder up to k possible cases.
Space Complexity: O(1), only a few variables are used.
1def smallestRepunitDivByK(k):
2 remainder = 0
3 for length in range(1, k + 1):
4 remainder = (remainder *
Using Python's simplicity, we loop up to k to find a valid divisible number with digits only '1'. The remainder pattern is checked, and once a zero remainder is found, the corresponding length is returned.
This approach still utilizes the modulus technique but introduces a digit construction method. Essentially, instead of just checking the length, we can construct the number step-by-step while simultaneously detecting cycles. The cycle detection ensures we do not repeat remainder calculations unnecessarily, identifying when no solution exists faster.
The goal remains to build a number consisting only of '1's that is divisible by k. The difference here is the emphasis on cycle and digit tracking during construction.
Time Complexity: O(k).
Space Complexity: O(k), due to the use of the visited_remainders array.
Here, we include an additional array to track each remainder used. A cycle is detected if the same remainder appears twice before finding a solution. Using visited_remainders, we store each state and verify conditions for possible cycles. This strategy optimizes cycle detection and avoids unnecessary computations.