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.
1#include <stdio.h>
2
3int smallestRepunitDivByK(int k) {
4 int remainder = 0;
5 for (int length = 1; length <= k; ++length) {
6 remainder = (remainder * 10 + 1) % k;
7 if (remainder == 0) return length;
8 }
9 return -1;
10}
11
12int main() {
13 int k = 3;
14 printf("%d\n", smallestRepunitDivByK(k));
15 return 0;
16}We start with a remainder of 0 and iterate up to k times, constructing the number step-by-step by updating the remainder. The formula remainder = (remainder * 10 + 1) % k helps us construct the number in the form of '111...1' without actually building this number explicitly. If we find a remainder of 0, the length of such a number is returned. If a cycle is detected, meaning all possible remainders are tried without success, -1 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.