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.
1function smallestRepunitDivByK(k) {
2 let remainder = 0;
3 for (let length = 1; length <= k; length++) {
4
In JavaScript, we use an iterative approach to keep constructing numbers using the remainder. The method effectively finds the smallest number made of '1's divisible by k by examining possible cycles within k tries.
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.
public class Solution {
public int SmallestRepunitDivByK(int k) {
int remainder = 0;
int[] visited = new int[k];
Array.Fill(visited, -1);
for (int length = 1; length <= k; length++) {
remainder = (remainder * 10 + 1) % k;
if (remainder == 0) return length;
if (visited[remainder] != -1) break;
visited[remainder] = length;
}
return -1;
}
public static void Main(string[] args) {
Solution solution = new Solution();
Console.WriteLine(solution.SmallestRepunitDivByK(3));
}
}C# uses arrays effectively for state tracking, supporting efficient cycle detection and constructive logic to find the solution length or determine unsolvability.