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.
1using System;
2
3public class Solution {
4 public int SmallestRepunitDivByK(int k) {
5 int remainder = 0;
6 for (int length = 1; length <= k; length++) {
7 remainder = (remainder * 10 + 1) % k;
8 if (remainder == 0) return length;
9 }
10 return -1;
11 }
12 public static void Main(string[] args) {
13 Solution solution = new Solution();
14 Console.WriteLine(solution.SmallestRepunitDivByK(3));
}
}The C# implementation works similarly by iterating through possible lengths and checking divisibility. The modulus operation is efficient for generating necessary remainders as part of the cycle check.
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.
In Python, tracking of visited remainders facilitates cycle detection and provides an effective exit condition for the iterative search. This pattern identification ensures early exits when needed.