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 =
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.
#include <vector>
using namespace std;
int smallestRepunitDivByK(int k) {
int remainder = 0;
vector<int> visited(k, -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;
}
int main() {
int k = 3;
cout << smallestRepunitDivByK(k) << endl;
return 0;
}This solution uses a vector to detect cycles by checking previously seen remainders. The solution iterates up to k while managing the digit construction and utilized state tracking to easily detect cycles.