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 <iostream>
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 std::cout << smallestRepunitDivByK(k) << std::endl;
return 0;
}This solution is identical to the C version but uses C++ I/O functions. We use modulus operation repeatedly to construct numbers with only '1's and determine their divisibility by k.
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.
Java's Arrays.fill is useful for initializing tracking arrays here, ensuring efficient cycle checks. The key is identifying repeated remainders, indicative of no possible solution within bounds.